Towards tight bounds on theta-graphs: more is not always better
From MaRDI portal
Publication:906396
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
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
