Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Local Routing in Sparse and Lightweight Geometric Graphs

Ashvinkumar, Vikrant ; Gudmundsson, Joachim LU ; Levcopoulos, Christos LU orcid ; Nilsson, Bengt J. and van Renssen, André (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:
author
; ; ; and
organization
publishing date
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}},
}