|
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 Cdel ≈
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
ρ · Cdel 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. |