Abstract: Highway is the backbone of a countrys transportation system. The highway development is very important to a country to overcome the demand for efficient road transportation. Better interconnected road network is crucial to increase the economic activities and social development in a country. The Malaysian government is highly committed towards the development of road network. Projek Lebuhraya Usahasama Berhad (PLUS) is one of the highway operators in Malaysia. It is also the largest highway concessionary or Build-Operate-Transfer (BOT) operator company in Malaysia. As the largest highway concessionary in Malaysia, the network analysis of PLUS highway development was studied in this study. The data used were based on the number of vehicles that enter and exit each PLUS toll Plazas from Juru (JRU) toll plaza to Skudai (SKD) toll plaza. The relationships between the toll plazas were studied by using minimal spanning trees and the overall centrality measures were used to determine the most influential toll plazas among the states. Based on the results, some recommendations are forwarded to the PLUS highway to improve the services and to increase the traffic efficiency.