Local Routing in Sparse and Lightweight Geometric Graphs
(2019) 30th International Symposium on Algorithms and Computation (ISAAC 2019) In LIPIcs – Leibniz International Proceedings in Informatics 149. p.1-30- 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 [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... (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 [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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/9c337412-5ee0-4e9e-88e2-8998e82af91e
- author
- Ashvinkumar, Vikrant ; Gudmundsson, Joachim LU ; Levcopoulos, Christos LU ; Nilsson, Bengt J. and van Renssen, André
- organization
- publishing date
- 2019-11-28
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Computational geometry, Spanners, Routing
- host publication
- 30th International Symposium on Algorithms and Computation (ISAAC 2019) : ISAAC 2019, December 8–11, 2019, Shanghai University of Finance and Economics, Shanghai, China - ISAAC 2019, December 8–11, 2019, Shanghai University of Finance and Economics, Shanghai, China
- series title
- LIPIcs – Leibniz International Proceedings in Informatics
- volume
- 149
- pages
- 13 pages
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 30th International Symposium on Algorithms and Computation (ISAAC 2019)
- conference location
- Shanghai, China
- conference dates
- 2019-12-09 - 2019-12-11
- external identifiers
-
- scopus:85076347211
- ISSN
- 1868-8969
- ISBN
- 978-3-95977-130-6
- DOI
- 10.4230/LIPIcs.ISAAC.2019.30
- language
- English
- LU publication?
- yes
- id
- 9c337412-5ee0-4e9e-88e2-8998e82af91e
- alternative location
- http://www.dagstuhl.de/dagpub/978-3-95977-130-6
- http://drops.dagstuhl.de/opus/volltexte/2019/30
- date added to LUP
- 2019-11-28 15:34:31
- date last changed
- 2022-04-10 22:48:28
@inproceedings{9c337412-5ee0-4e9e-88e2-8998e82af91e, 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 [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.}}, author = {{Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, André}}, booktitle = {{30th International Symposium on Algorithms and Computation (ISAAC 2019) : ISAAC 2019, December 8–11, 2019, Shanghai University of Finance and Economics, Shanghai, China}}, isbn = {{978-3-95977-130-6}}, issn = {{1868-8969}}, keywords = {{Computational geometry; Spanners; Routing}}, language = {{eng}}, month = {{11}}, pages = {{1--30}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, series = {{LIPIcs – Leibniz International Proceedings in Informatics}}, title = {{Local Routing in Sparse and Lightweight Geometric Graphs}}, url = {{http://dx.doi.org/10.4230/LIPIcs.ISAAC.2019.30}}, doi = {{10.4230/LIPIcs.ISAAC.2019.30}}, volume = {{149}}, year = {{2019}}, }