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

DOI10.1007/BF01758846MaRDI QIDQ1194346zbMATH OpenOpenAlexFDO

Authors Christos Levcopoulos, Andrzej Lingas

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

Delaunay triangulationspanning treetime complexityplanar straight-line graphcomplete Euclidean graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4155926
• There are planar graphs almost as good as the complete graph
• Delaunay graphs are almost as good as complete graphs
• scientific article; zbMATH DE number 4155925
• scientific article; zbMATH DE number 140458

Cites work

• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 140458 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A note on Delaunay and optimal triangulations
• Delaunay graphs are almost as good as complete graphs
• Finding Minimum Spanning Trees

Cited in

(19)

• On certain geometric properties of the Yao-Yao graphs
• Sparse geometric graphs with small dilation
• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• scientific article; zbMATH DE number 4155926 (Why is no real title available?)
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Delaunay graphs are almost as good as complete graphs
• Sparse hop spanners for unit disk graphs
• Lattice spanners of low degree
• Minimum weight convex Steiner partitions
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• There are planar graphs almost as good as the complete graph
• Lattice spanners of low degree
• Light orthogonal networks with constant geometric dilation
• Balancing minimum spanning trees and shortest-path trees
• On plane geometric spanners: a survey and open problems
• Lower bounds on the dilation of plane spanners
• Computing a minimum-dilation spanning tree is NP-hard
• Local routing in sparse and lightweight geometric graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194346)