The minimum spanning tree problem on a planar graph

Finding a spanning tree of minimum weight is one of the best known graph problems. Several efficient algorithms exist for solving this problem [3-5, 7, 9]. This note presents a linear time algorithm for the minimum spanning tree problem on a planar graph. Cheriton and Tarjan have proposed a linear time algorithm for this problem. The time complexity of our algorithm is the same as that of Cheriton and Tarjan’s algorithm. Different from Cheriton and Tarjan’s algorithm, the present algorithm does not require the clean-up activity. So, the implementation of the algorithm is very easy. The present algorithm maintains a pair of planar graph and its dual graph and breeds both a minimum spanning tree of the original graph and a maximum spanning tree of a dual graph. In each iteration of the algorithm, either the number of edges decreases or a vertex of the planar graph or its dual graph is deleted. By employing a simple bucket structure, the paper can save the time complexity of every iteration to O(1).