Perkovic, Ljubomir ;
Kanj, Iyad A.
On Geometric Spanners of Euclidean and Unit Disk Graphs
Abstract
We consider the problem of constructing boundeddegree planar
geometric spanners of Euclidean and unitdisk 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 adhoc networks. We obtain a very
simple distributed, {em strictlylocalized 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 = {409420},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1320},
URN = {urn:nbn:de:0030drops13200},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1320},
annote = {Keywords: Geometric spanner, euclidean graph, unit disk graph, wireless adhoc networks}
}
Keywords: 

Geometric spanner, euclidean graph, unit disk graph, wireless adhoc networks 
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2008 
Date of publication: 

06.02.2008 