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é (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:
author
; ; ; and
organization
publishing date
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}},
}