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

DOI10.1016/J.TCS.2015.12.017zbMATH Open1334.68237arXiv1404.6233OpenAlexW1863587147MaRDI QIDQ906396FDOQ906396

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

Publication date: 21 January 2016

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

Abstract: We present improved upper and lower bounds on the spanning ratio of $heta$-graphs with at least six cones. Given a set of points in the plane, a $heta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $heta=2pi/m$, and adds an edge to the `closest' vertex in each cone. We show that for any integer $kgeq1$, $heta$-graphs with $4k+2$ cones have a spanning ratio of $1+2sin(heta/2)$ and we provide a matching lower bound, showing that this spanning ratio tight. Next, we show that for any integer $kgeq1$, $heta$-graphs with $4k+4$ cones have spanning ratio at most $1+2sin(heta/2)/(cos(heta/2)-sin(heta/2))$. We also show that $heta$-graphs with $4k+3$ and $4k+5$ cones have spanning ratio at most $cos(heta/4)/(cos(heta/2)-sin(3heta/4))$. This is a significant improvement on all families of $heta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $heta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. These spanning proofs also imply improved upper bounds on the competitiveness of the $heta$-routing algorithm. In particular, we show that the $heta$-routing algorithm is $(1+2sin(heta/2)/(cos(heta/2)-sin(heta/2)))$-competitive on $heta$-graphs with $4k+4$ cones and that this ratio is tight. Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of $heta$-graphs. In particular, we show that $heta$-graphs with $4k+4$ cones have spanning ratio at least $1+2an(heta/2)+2a{n}^2(heta/2)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $heta$-graphs with $4k+4$ cones is greater than that of $heta$-graphs with $4k+2$ cones, showing that increasing the number of cones can make the spanning ratio worse.

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

Recommendations

• On the spanning ratio of theta-graphs
• The price of order
• The price of order
• Upper bounds on the spanning ratio of constrained theta-graphs
• The \(\theta_5\)-graph is a spanner

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)

Cites Work

• Geometric Spanner Networks
• There are planar graphs almost as good as the complete graph
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• On plane geometric spanners: a survey and open problems
• Competitive routing in the half-\(\theta_6\)-graph
• On the stretch factor of the theta-4 graph
• On the spanning ratio of theta-graphs
• Title not available (Why is that?)
• Theta-3 is connected
• The \(\varTheta_5\)-graph is a spanner

Cited In (29)

• Ordered theta graphs
• Routing in polygonal domains
• Improved bounds on the spanning ratio of the theta-5-graph
• On the spanning and routing ratios of the directed \(\varTheta_6\)-graph
• Upper bounds on the spanning ratio of constrained theta-graphs
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• Local routing algorithms on Euclidean spanners with small diameter
• On the spanning and routing ratio of Theta-Four
• On the stretch factor of the theta-4 graph
• On the spanning ratio of theta-graphs
• The \(\theta_5\)-graph is a spanner
• On the average number of edges in theta graphs
• Routing on heavy path WSPD spanners
• On the spanning and routing ratios of the directed \(\Theta_6\)-graph
• The \(\varTheta_5\)-graph is a spanner
• Spanning properties of Theta-Theta-6
• The stretch-length tradeoff in geometric networks: average case and worst case study
• Improved spanning ratio of the Theta-5 graph
• Online Spanners in Metric Spaces
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Spanning properties of Yao and \(\theta\)-graphs in the presence of constraints
• Generalized sweeping line spanners
• Routing among convex polygonal obstacles in the plane
• The price of order
• The price of order
• Generalized sweeping line spanners
• Emanation graph: a plane geometric spanner with Steiner points
• Construction and Local Routing for Angle-Monotone Graphs
• On the spanning and routing ratio of the directed theta-four graph

This page was built for publication: Towards tight bounds on theta-graphs: more is not always better

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