Abstract

Title: On Geometric Spanners of Euclidean Graphs and their Applications in Wireless Networks
Published: August 2007
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 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.
Full Paper: [pdf]