2026-07-22T18:35:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1320 2024-03-06T10:33:00Z ddc:004 open_access

On Geometric Spanners of Euclidean and Unit Disk Graphs Perkovic, Ljubomir Kanj, Iyad A. Geometric spanner euclidean graph unit disk graph wireless ad-hoc networks 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_{delapprox 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 $ ho =1+2pi(kcos{frac{pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $kgeq 14$. This result immediately implies an algorithm for constructing a planar geometric spanner of a Euclidean graph with stretch factor $ ho cdot C_{del$ and degree bounded by $k$, for any integer parameter $kgeq 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ljubomir Perkovic and Iyad A. Kanj 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1320 urn:nbn:de:0030-drops-13200 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1320 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode