A phasor measurement unit (PMU) is considered to have the potential to improve the efficiency of electric power systems by monitoring, control, and protection. Through measurements of all bus voltages, incoming and outgoing currents, and by subsequent calculation of all phase angles, employing PMUs on every substation in a power system will allow complete observation of a power system. However, having a PMU on every substation may not be economically feasible. Therefore, methodologies must be devised that can monitor a system with the minimum possible number of PMUs. In this paper, we propose six graph theoretical PMU placement heuristics. The proposed heuristics overcome the previous approaches in terms of scalability and execution time. The proposed heuristics are thoroughly compared and benchmarked using standard IEEE bus networks ranging from 14 to 300 buses, and a 2,383 bus system.