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/
Perkovic, Ljubomir ;
Kanj, Iyad A.
On Geometric Spanners of Euclidean and Unit Disk Graphs
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 |