License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1320/
Go to the corresponding LIPIcs Volume Portal

Perkovic, Ljubomir ; Kanj, Iyad A.

On Geometric Spanners of Euclidean and Unit Disk Graphs

pdf-format:
22011.PerkovicLjubomir.Paper.1320.pdf (0.2 MB)

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 =		{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
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI