2026-08-12T05:29:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11526 2024-03-06T10:48:13Z ddc:004 open_access

Local Routing in Sparse and Lightweight Geometric Graphs Ashvinkumar, Vikrant Gudmundsson, Joachim Levcopoulos, Christos Nilsson, Bengt J. van Renssen, André Computational geometry Spanners Routing Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Bose and Morin, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikrant Ashvinkumar and Joachim Gudmundsson and Christos Levcopoulos and Bengt J. Nilsson and André van Renssen 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.30 urn:nbn:de:0030-drops-115269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.30 eng https://creativecommons.org/licenses/by/3.0/legalcode