NDLI: On Spanners and Lightweight Spanners of Geometric Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kanj, Iyad A. Xia, Ge Perkovi, Ljubomir
Copyright Year	2010
Abstract	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.
Starting Page	2132
Ending Page	2161
Page Count	30
File Format	PDF
ISSN	00975397
DOI	10.1137/080737708
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	6 (Special Section On Foundations of Computer Science)
Volume Number	39
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2010-03-12
Access Restriction	Subscribed
Subject Keyword	Planar graphs; geometric and topological aspects of graph theory unit disk graphs bounded degree Delaunay triangulations Computer graphics; computational geometry spanners local distributed algorithms Distributed algorithms lightweight
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Angles of Planar Triangular Graphs

Low-Degree Spanning Trees of Small Weight

Robust Geometric Spanners

Representations of Graphs on a Cylinder

DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

On geometric spanners of Euclidean and unit disk graphs (2008)

On geometric spanners of euclidean and unit disk graphs (2008).

Strictly localized construction of planar bounded-degree spanners of unit disk graphs.

On Geometric Spanners of Euclidean and Unit Disk Graphs (2008)

On Spanners and Lightweight Spanners of Geometric Graphs

Similar Documents

Angles of Planar Triangular Graphs

Low-Degree Spanning Trees of Small Weight

Robust Geometric Spanners

Representations of Graphs on a Cylinder

DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

On geometric spanners of Euclidean and unit disk graphs (2008)

On geometric spanners of euclidean and unit disk graphs (2008).

Strictly localized construction of planar bounded-degree spanners of unit disk graphs.

On Geometric Spanners of Euclidean and Unit Disk Graphs (2008)

On Spanners and Lightweight Spanners of Geometric Graphs