ON SPANNERS AND LIGHTWEIGHT SPANNERS OF GEOMETRIC GRAPHS

We consider the problem of computing spanners of Euclidean and unit disk graphs embedded in the two-dimensional Euclidean plane. We are particularly interested in spanners that possess useful properties such as planarity, bounded degree, and/or light weight. Such spanners have been extensively studi...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2010-01, Vol.39 (6), p.2132-2161
Main Authors: KANJ, Iyad A, PERKOVIC, Ljubomir, GE XIA
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Computation
Computational mathematics
Computer science
control theory
systems
Disks
Distributed processing
Euclidean space
Exact sciences and technology
Graphs
Information retrieval. Graph
Lightweight
Mathematical models
Mathematics
Miscellaneous
Numerical analysis
Numerical analysis. Scientific computation
Numerical approximation
Pattern recognition. Digital image processing. Computational geometry
Planes
Sciences and techniques of general use
Studies
Theoretical computing
Weight reduction
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of computing spanners of Euclidean and unit disk graphs embedded in the two-dimensional Euclidean plane. We are particularly interested in spanners that possess useful properties such as planarity, bounded degree, and/or light weight. Such spanners have been extensively studied in the area of computational geometry and have been used as the building block for constructing efficient and reliable wireless network communication topologies. We study the above problem under two computational models: the centralized and the distributed model. In the distributed model we focus on algorithms that are local. Such algorithms are suitable for the relevant applications (e.g., wireless computing). Under the centralized model, we present an O(n lg n) time algorithm that computes a bounded-degree plane spanner of a complete Euclidean graph, where n is the number of points in the graph. Both upper bounds on the degree and the stretch factor significantly improve the previous bounds. We extend this algorithm to compute a bounded-degree plane lightweight spanner of a complete Euclidean graph. Under the distributed model, we give the first local algorithm for computing a spanner of a unit disk graph that is of bounded degree and plane. The upper bounds on the degree, stretch factor, and the locality of the algorithm dramatically improve the previous results, as shown in the paper. This algorithm can also be extended to compute a bounded-degree plane lightweight spanner of a unit disk graph. Our algorithms rely on structural and geometric results that we develop in this paper. [PUBLICATION ABSTRACT]
ISSN:0097-5397
1095-7111
DOI:10.1137/080737708