Loading...
Please wait, while we are loading the content...
Similar Documents
On Geometric Spanners of Euclidean and Unit Disk Graphs (2008)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kanj, Iyad A. Perkovic, Ljubomir |
| Description | 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 Cdel ≈ 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 ρ = 1 + 2π(k cos π 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. 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, 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. |
| File Format | |
| Language | English |
| Publisher Date | 2008-01-01 |
| Publisher Institution | IN "25TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS |
| Access Restriction | Open |
| Subject Keyword | Euclidean Minimum Spanning Tree Planar Geometric Spanner Unit-disk Graph Integer Parameter Structural Result Wireless Ad-hoc Network Previous Result First Result Stretch Factor Euclidean Graph Degree Bound Bounded-degree Planar Geometric Spanner Simple Linear Time Algorithm Second Contribution Unit Disk Graph Obtained Result Strictly-localized Algorithm Usual Model Delaunay Subgraph Stretch Factor Cdel Delaunay Graph Geometric Spanner |
| Content Type | Text |
| Resource Type | Article |
