Local routing in sparse and lightweight geometric graphs

DOI10.1007/s00453-022-00930-2OpenAlexW4210746858MaRDI QIDQ2134745

Vikrant Ashvinkumar, Christos Levcopoulos, André van Renssen, Bengt J. Nilsson, Joachim Gudmundsson

Publication date: 3 May 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryroutingspanners

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Delaunay graphs are almost as good as complete graphs
• Greedy drawings of triangulations
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• On sparse spanners of weighted graphs
• There are plane spanners of degree 4 and moderate stretch factor
• Upper and lower bounds for online routing on Delaunay triangulations
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
• Towards plane spanners of degree 3
• Degree four plane spanners: Simpler and better
• Efficient Construction of Low Weight Bounded Degree Planar Spanner
• Geometric Spanner Networks
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
• Online Routing in Triangulations
• The Greedy Spanner Is Existentially Optimal
• Greedy spanners are optimal in doubling metrics
• Local Routing in Sparse and Lightweight Geometric Graphs
• Lower Bounds on the Dilation of Plane Spanners
• An Algorithm to Construct Greedy Drawings of Triangulations

This page was built for publication: Local routing in sparse and lightweight geometric graphs