Technical report: an application of graph theory in place a sensor at traffic light / Nur Shamimi Saleh Huddin, Nurul Nadiah Abd Ghani and Wan Nur Hafawati Wan Hassan

Placing a sensor at traffic light is currently an important issue to avoid collision among the transportation on the road. The sensor need to been placed at a right way so that the sensor will collect the information needed by Jabatan Kerja Raya to take action on any problem involved. In this study, the basic application of Graph Theory for Traffic Control is used to develop the compatibility graph, find the minimal edge set and draw the connectivity graph. We consider the streams at Jalan Membunga, Machang to be focus on in this study. The purpose of developing the compatibility graph is to obtain the minimum edge control set and draw the connectivity graph. The compatibility graph is obtained where there are 12 labeled vertices and 36 edges that connect the vertices. Next, it was found that the set of edge control of compatibility graph is not unique. Then, it is important to get the set of minimal edge control by using an algorithm. We got 4 edges connectivity of compatibility graph which are (a,c), (b,c), (c,g), (c,j) means that the sensors can be placed on the first, third, and fourth phase in the traffic light streams. After that, we obtained the connectivity graph by removing the 4 minimal edges connectivity from compatibility graph. As a conclusion, developing the compatibility graph is important in finding minimum edge control set and connectivity graph so that we can place the sensors in the right place at the traffic light.