EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION

DOI10.1142/S0218195907002318zbMath1185.68775MaRDI QIDQ5297793

Rolf Klein, Ansgar Grüne, Christian Knauer, Annette Ebbers-Baumann, Andrzej Lingas, Marek Karpinski

Publication date: 13 July 2007

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

dilationlower boundplane graphgeometric networkstretch factorspanning ratio

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On plane geometric spanners: a survey and open problems, Most finite point sets in the plane have dilation \(>1\)

Cites Work

• Delaunay graphs are almost as good as complete graphs
• Classes of graphs which approximate the complete Euclidean graph
• A fast algorithm for approximating the detour of a polygonal chain.
• Geometric Spanner Networks