On Geometric Spanners of Euclidean and Unit Disk Graphs

Authors Ljubomir Perkovic, Iyad A. Kanj



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1320.pdf
  • Filesize: 186 kB
  • 12 pages

Document Identifiers

Author Details

Ljubomir Perkovic
Iyad A. Kanj

Cite AsGet BibTex

Ljubomir Perkovic and Iyad A. Kanj. On Geometric Spanners of Euclidean and Unit Disk Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 409-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1320

Abstract

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.
Keywords
  • Geometric spanner
  • euclidean graph
  • unit disk graph
  • wireless ad-hoc networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail