Projects have increasingly become organizations’ strategic initiatives to implement changes and improve organizational performance. Concerned over constrained resources and rapid changes that exist in the project environment, project portfolio management (PPM) can support organizations in prioritizing and selecting the right projects to meet strategic objectives and improve project success rates. This research aims to investigate and analyze the application of PPM in relation to project success in Australia by conducting a questionnaire survey with 64 senior project, program and portfolio managers from industry sectors across Australia. Graph Theoretic Approach (GTA) is employed as an analysis method to generate prioritization of the relationships between PPM practices and project success criteria. Twenty-five PPM practices are grouped into four categories and examined against seven project success criteria. The findings show that each group interacts with success criteria at a diverse range. These provide organizations with implications to benchmark their PPM practices with the current findings, especially those that strongly contribute to success in project implementation and outcomes. Furthermore, the results highlight integrated concepts and application between project success and portfolio management.