zbMATH — the first resource for mathematics

The minimum spanning tree problem on a planar graph. (English) Zbl 0823.05024
A minimum weight spanning tree algorithm for planar graphs with time complexity \(O(n)\) is given. The algorithm maintains a pair of a planar graph and its dual graph and breeds both a minimum spanning tree for the original graph and a maximum spanning tree of its dual. The author claims that his algorithm is easy to implement compared to other existing algorithms for the problem which have the same time complexity.

05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Cheriton, D.; Tarjan, R.E., Finding minimum spanning trees, SIAM J. comput., 5, 724-742, (1976) · Zbl 0358.90069
[2] Chiba, N.; Nishizeki, T.; Saito, N., Efficient algorithms for graph alterations, Trans. IECE J64-D, 934-939, (1981), (in Japanese)
[3] Dijkstra, E.W., A note on two problems in connection with graphs, Numer. math., 1, 269-271, (1959) · Zbl 0092.16002
[4] Fredman, M.L.; Tarjan, R.E., Fibonacci heaps and their uses in improved network optimization problems, J. ACM, 34, 596-615, (1987) · Zbl 1412.68048
[5] Gabow, H.N.; Galil, Z.; Spencer, T.; Tarjan, R.E., Efficient algorithms for finding minimum spanning trees in undirected trees in undirected and directed graphs, Combinatorica, 6, 109-122, (1986) · Zbl 0608.05027
[6] Hopcroft, J.E.; Tarjan, R.E., Efficient planarity testing, J. ACM, 21, 549-568, (1974) · Zbl 0307.68025
[7] Kruskal, J.B., On the shortest spanning subtree of a graph and the travelling salesman problem, (), 48-50 · Zbl 0070.18404
[8] Lawler, E.L., Combinatorial optimization: networks an matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0413.90040
[9] Prim, R.C., Shortest connection networks and some generalizations, Bell system tech. J., 36, 1389-1401, (1957)
[10] Whitney, H., On the abstract properties of linear dependence, Amer. J. math., 57, 509-533, (1935) · JFM 61.0073.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.