Towards tight bounds on theta-graphs: more is not always better

DOI10.1016/j.tcs.2015.12.017zbMath1334.68237arXiv1404.6233OpenAlexW1863587147MaRDI QIDQ906396

André van Renssen, Jean-Lou De Carufel, Pat Morin, Prosenjit Bose, Sander Verdonschot

Publication date: 21 January 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryspannersspanning ratiotight boundstheta-graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Improved bounds on the spanning ratio of the theta-5-graph ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ Routing in polygonal domains ⋮ Spanning properties of Theta-Theta-6 ⋮ Generalized sweeping line spanners ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Generalized sweeping line spanners ⋮ Online Spanners in Metric Spaces ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Construction and Local Routing for Angle-Monotone Graphs ⋮ The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ The Price of Order ⋮ The Price of Order

Cites Work

• On plane geometric spanners: a survey and open problems
• Theta-3 is connected
• There are planar graphs almost as good as the complete graph
• The \(\varTheta_5\)-graph is a spanner
• On the Stretch Factor of the Theta-4 Graph
• On the Spanning Ratio of Theta-Graphs
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Geometric Spanner Networks
• Unnamed Item
• Unnamed Item