License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1320
URN: urn:nbn:de:0030-drops-13200
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1320/

Perkovic, Ljubomir ; Kanj, Iyad A.

On Geometric Spanners of Euclidean and Unit Disk Graphs

pdf-format:
Dokument 1.pdf (187 KB)


Abstract

We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{delapprox 2.42$; however, its degree may not be bounded. Our first result is a very simple linear time algorithm for constructing a subgraph of the Delaunay graph with stretch factor $ ho =1+2pi(kcos{frac{pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $kgeq 14$. This result immediately implies an algorithm for constructing a planar geometric spanner of a Euclidean graph with stretch factor $ ho cdot C_{del$ and degree bounded by $k$, for any integer parameter $kgeq 14$. Moreover, the resulting spanner contains a Euclidean Minimum Spanning Tree (EMST) as a subgraph. Our second contribution lies in developing the structural results necessary to transfer our analysis and algorithm from Euclidean graphs to unit disk graphs, the usual model for wireless ad-hoc networks. We obtain a very simple distributed, {em strictly-localized algorithm that, given a unit disk graph embedded in the plane, constructs a geometric spanner with the above stretch factor and degree bound, and also containing an EMST as a subgraph. The obtained results dramatically improve the previous results in all aspects, as shown in the paper.

BibTeX - Entry

@InProceedings{perkovic_et_al:LIPIcs:2008:1320,
  author =	{Ljubomir Perkovic and Iyad A. Kanj},
  title =	{{On Geometric Spanners of Euclidean and Unit Disk Graphs}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{409--420},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1320},
  URN =		{urn:nbn:de:0030-drops-13200},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1320},
  annote =	{Keywords: Geometric spanner, euclidean graph, unit disk graph, wireless ad-hoc networks}
}

Keywords: Geometric spanner, euclidean graph, unit disk graph, wireless ad-hoc networks
Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2008
Date of publication: 06.02.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI