On Geometric Spanners of Euclidean and Unit Disk Graphs

Details On Geometric Spanners of Euclidean and Unit Disk Graphs On Geometric Spanners of Euclidean and Unit Disk Graphs

2008-02-20

arxiv.org/abs/0802.2864v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Data Structures and Algorithms

Scientific paper

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_{del\approx 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 $\rho =1+2\pi(k\cos{\frac{\pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $k\geq 14$. This result immediately implies an algorithm for constructing a planar geometric spanner of a Euclidean graph with stretch factor $\rho \cdot C_{del$ and degree bounded by $k$, for any integer parameter $k\geq 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.

Affiliated with

Also associated with

No associations

Rating

On Geometric Spanners of Euclidean and Unit Disk Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Geometric Spanners of Euclidean and Unit Disk Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Geometric Spanners of Euclidean and Unit Disk Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647874