The Price of Order

DOI10.1142/S0218195916600013zbMath1409.05155arXiv1602.00399MaRDI QIDQ5892451

Pat Morin, André van Renssen, Prosenjit Bose

Publication date: 19 May 2017

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

Full work available at URL: https://arxiv.org/abs/1602.00399

zbMATH Keywords

geometric graphsspannersstretch factorspanning ratiotight bounds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Theta-3 is connected
• Ordered theta graphs
• Towards tight bounds on theta-graphs: more is not always better
• There are planar graphs almost as good as the complete graph
• On the Stretch Factor of the Theta-4 Graph
• The θ 5-Graph is a Spanner
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Geometric Spanner Networks
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles