Local routing in sparse and lightweight geometric graphs

DOI10.1007/S00453-022-00930-2MaRDI QIDQ2134745zbMATH OpenOpenAlexFDO

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

Publication date 3 May 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• Local Routing in Sparse and Lightweight Geometric Graphs
• Improved routing on the Delaunay triangulation
• Upper and lower bounds for online routing on Delaunay triangulations
• Upper and lower bounds for online routing on Delaunay triangulations
• Improved routing on the Delaunay triangulation

Cites work

• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 910877 (Why is no real title available?)
• A note on two problems in connexion with graphs
• An Algorithm to Construct Greedy Drawings of Triangulations
• Computational geometry. Algorithms and applications.
• Degree four plane spanners: simpler and better
• Delaunay graphs are almost as good as complete graphs
• Efficient construction of low weight bounded degree planar spanner
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Geometric Spanner Networks
• Greedy drawings of triangulations
• Greedy spanners are optimal in doubling metrics
• Improved routing on the Delaunay triangulation
• Local Routing in Sparse and Lightweight Geometric Graphs
• Lower bounds on the dilation of plane spanners
• On sparse spanners of weighted graphs
• Online Routing in Triangulations
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• The greedy spanner is existentially optimal
• The stretch factor of the Delaunay triangulation is less than 1.998
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• There are plane spanners of degree 4 and moderate stretch factor
• Towards plane spanners of degree 3
• Upper and lower bounds for online routing on Delaunay triangulations

Cited in

(7)

• On a family of strong geometric spanners that admit local routing strategies
• Local Routing in Sparse and Lightweight Geometric Graphs
• Dynamic routing schemes for graphs with low local density
• Local routing in a tree metric 1-spanner
• Lightweight paths in graphs
• On local routing of two-terminal nets
• Construction and Local Routing for Angle-Monotone Graphs

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

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