The minimum spanning tree problem on a planar graph

DOI10.1016/0166-218X(94)00095-UzbMath0823.05024MaRDI QIDQ1805468

Tomomi Matsui

Publication date: 14 June 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

planar graphsspanning treetime complexityminimum weight spanning treegraphical algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Faster shortest paths in dense distance graphs, with applications ⋮ The saga of minimum spanning trees ⋮ Contracting a Planar Graph Efficiently

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Efficient Planarity Testing
• Finding Minimum Spanning Trees
• Fibonacci heaps and their uses in improved network optimization algorithms
• Unnamed Item

This page was built for publication: The minimum spanning tree problem on a planar graph