There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

DOI10.1007/BF01758846zbMath0764.05021OpenAlexW2029772672MaRDI QIDQ1194346

Andrzej Lingas, Christos Levcopoulos

Publication date: 27 September 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758846

zbMATH Keywords

spanning treetime complexityDelaunay triangulationplanar straight-line graphcomplete Euclidean graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)

Related Items (15)

Sparse hop spanners for unit disk graphs ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Balancing minimum spanning trees and shortest-path trees ⋮ EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER ⋮ On plane geometric spanners: a survey and open problems ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ Unnamed Item ⋮ An efficient parallel algorithm for shortest paths in planar layered digraphs ⋮ Sparse geometric graphs with small dilation ⋮ Computing a minimum-dilation spanning tree is NP-hard ⋮ Minimum weight convex Steiner partitions ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Light orthogonal networks with constant geometric dilation ⋮ Lattice spanners of low degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• A note on Delaunay and optimal triangulations
• Finding Minimum Spanning Trees

This page was built for publication: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees