On the spanning and routing ratio of the directed theta-four graph
From MaRDI portal
Publication:6124828
DOI10.1007/s00454-023-00597-8MaRDI QIDQ6124828
Darryl Hill, Jean-Lou De Carufel, Prosenjit Bose, Michiel H. M. Smid
Publication date: 2 April 2024
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Unnamed Item
- Theta-3 is connected
- Memoryless routing in convex subdivisions: random walks are optimal
- 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
- Competitive online routing in geometric graphs
- On the spanning and routing ratios of the directed \(\Theta_6\)-graph
- The \(\varTheta_5\)-graph is a spanner
- Bounding the locality of distributed routing algorithms
- Upper and lower bounds for online routing on Delaunay triangulations
- Efficiently navigating a random Delaunay triangulation
- On the Stretch Factor of the Theta-4 Graph
- Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
- Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
- Online Routing in Triangulations
- Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs
This page was built for publication: On the spanning and routing ratio of the directed theta-four graph
