On Spanners and Lightweight Spanners of Geometric Graphs

DOI10.1137/080737708zbMath1221.05294OpenAlexW2018527525MaRDI QIDQ3068627

Ljubomir Perković, Ge Xia, Iyad A. Kanj

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5bf7bfed49c03ed20b11c25f4d27599da57e91df

zbMATH Keywords

Delaunay triangulationsspannersbounded degreeunit disk graphslightweightlocal distributed algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (6)

On plane geometric spanners: a survey and open problems ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ On bounded degree plane strong geometric spanners ⋮ Improved spanning ratio for low degree plane spanners ⋮ Improved local algorithms for spanner construction

This page was built for publication: On Spanners and Lightweight Spanners of Geometric Graphs