On the spanning and routing ratios of the directed \(\Theta_6\)-graph

DOI10.1016/j.comgeo.2022.101881zbMath1491.05059OpenAlexW4226118606WikidataQ114195526 ScholiaQ114195526MaRDI QIDQ2144459

Prosenjit Bose, Hugo A. Akitaya, Ahmad Biniaz

Publication date: 13 June 2022

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2022.101881

zbMATH Keywords

online routingspanning ratio\(\Theta_k\)-graphsrouting ratio

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

On the spanning and routing ratio of the directed theta-four graph ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Theta-3 is connected
• Improved bounds on the spanning ratio of the theta-5-graph
• Towards tight bounds on theta-graphs: more is not always better
• Classes of graphs which approximate the complete Euclidean graph
• 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
• Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Geometric Spanner Networks
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
• Probability on Graphs
• Online Routing in Triangulations
• Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs
• On the Spanning and Routing Ratio of Theta-Four