Title: |
On Geometric Spanners of Euclidean Graphs and their
Applications in Wireless Networks |

Authors: |
Iyad A. Kanj, Ljubomir Perkovic |

Abstract: |
We consider the problem of constructing a bounded-degree
planar geometric spanner for a unit disk graph modeling a wireless
network. The related problem of constructing a planar geometric spanner
of a Euclidean graph has been extensively studied in the literature. It
is well known that the Delaunay subgraph is a planar geometric spanner
with stretch factor C_{del} ≈
2.42; however, its degree may not be bounded. Significant work
has been done on developing algorithms for constructing bounded-degree
planar geometric spanners of Euclidean graphs. Our first result presents
a very simple linear time algorithm for constructing a subgraph of the
Delaunay graph with stretch factor ρ
=1+2π(k cos{π
\over k})^{-1} and degree bounded by k, for any
integer parameter k ≥ 14.
This result immediately implies an algorithm for constructing a planar
geometric spanner of a Euclidean graph with stretch factor
ρ · C_{del} and degree
bounded by k, for any integer parameter k
≥ 14. Our second contribution lies
in developing the structural results necessary to transfer our analysis
and algorithm from Euclidean graphs to unit disk graphs. We obtain a
very simple strictly-localized algorithm that, given a unit disk graph
embedded in the plane, constructs a planar geometric spanner with the
above stretch factor and degree bound. The two results dramatically
improve the previous results in all aspects, as shown in the paper. |

Full Paper: |
[pdf] |