Local Routing in Sparse and Lightweight Geometric Graphs
(2022) In Algorithmica 84(5). p.1316-1340- Abstract
- 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 (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Ω(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... (More)
- 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 (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Ω(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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/0a4370b8-879d-431d-868f-2985b0dbcfb7
- author
- Ashvinkumar, Vikrant ; Gudmundsson, Joachim LU ; Levcopoulos, Christos LU ; Nilsson, Bengt J. and van Renssen, André
- organization
- publishing date
- 2022-01-25
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Algorithmica
- volume
- 84
- issue
- 5
- pages
- 1316 - 1340
- publisher
- Springer
- external identifiers
-
- scopus:85123504940
- ISSN
- 0178-4617
- DOI
- 10.1007/s00453-022-00930-2
- language
- English
- LU publication?
- yes
- id
- 0a4370b8-879d-431d-868f-2985b0dbcfb7
- date added to LUP
- 2022-01-26 17:25:08
- date last changed
- 2022-06-30 16:24:12
@article{0a4370b8-879d-431d-868f-2985b0dbcfb7, abstract = {{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 (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Ω(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.}}, author = {{Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, André}}, issn = {{0178-4617}}, language = {{eng}}, month = {{01}}, number = {{5}}, pages = {{1316--1340}}, publisher = {{Springer}}, series = {{Algorithmica}}, title = {{Local Routing in Sparse and Lightweight Geometric Graphs}}, url = {{http://dx.doi.org/10.1007/s00453-022-00930-2}}, doi = {{10.1007/s00453-022-00930-2}}, volume = {{84}}, year = {{2022}}, }