On the spanning and routing ratios of the directed _6-graph

DOI10.1016/J.COMGEO.2022.101881zbMATH Open1491.05059OpenAlexW4226118606WikidataQ114195526 ScholiaQ114195526MaRDI QIDQ2144459FDOQ2144459

Authors Hugo A. Akitaya, Ahmad Biniaz, Prosenjit Bose

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)

Recommendations

• On the spanning and routing ratios of the directed \(\varTheta_6\)-graph
• Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs
• Competitive routing in the half-\(\theta_6\)-graph
• On the spanning ratio of theta-graphs
• On large (Δ, 6)-Graphs
• Spanning properties of Theta-Theta-6
• scientific article; zbMATH DE number 2119746
• Roundtrip spanners and roundtrip routing in directed graphs
• The 6-girth-thickness of the complete graph
• Upper bounds on the spanning ratio of constrained theta-graphs

Cites work

• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• A note on two problems in connexion with graphs
• Classes of graphs which approximate the complete Euclidean graph
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Geometric Spanner Networks
• Improved bounds on the spanning ratio of the theta-5-graph
• On the spanning and routing ratio of Theta-Four
• On the stretch factor of the theta-4 graph
• Online Routing in Triangulations
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• Probability on graphs. Random processes on graphs and lattices.
• The \(\varTheta_5\)-graph is a spanner
• There are planar graphs almost as good as the complete graph
• Theta-3 is connected
• Towards tight bounds on theta-graphs: more is not always better

Cited in

(8)

• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
• On the spanning and routing ratio of Theta-Four
• Spanning properties of Theta-Theta-6
• Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• Competitive routing in the half-\(\theta_6\)-graph
• On the spanning and routing ratio of the directed theta-four graph

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: On the spanning and routing ratios of the directed \(\Theta_6\)-graph

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