On Geometric Spanners of Euclidean and Unit Disk Graphs
| dc.creator | Kanj, Iyad A. | |
| dc.creator | Perkovic, Ljubomir | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:22:04Z | |
| dc.date.available | 2026-07-07T09:22:04Z | |
| dc.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 $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 $ρ=1+2π(k\cos{\frac{π{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 $ρ\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. | |
| dc.identifier | https://arxiv.org/abs/0802.2864 | |
| dc.identifier | http://arxiv.org/abs/0802.2864 | |
| dc.identifier | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155248 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | On Geometric Spanners of Euclidean and Unit Disk Graphs | |
| dc.type | text |