On spanners and lightweight spanners of geometric graphs

DOI10.1137/080737708MaRDI QIDQ3068627zbMATH OpenOpenAlexFDO

Authors Ljubomir Perković, Ge Xia, Iyad 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 triangulationsbounded degreespannersunit disk graphslightweightlocal distributed algorithms

Mathematics Subject Classification ID

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

Recommendations

• On Spanners of Geometric Graphs
• Computing Lightweight Spanners Locally
• On geometric spanners of Euclidean and unit disk graphs
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Efficient construction of low weight bounded degree planar spanner

Cited in

(22)

• Packing short plane spanning trees in complete geometric graphs
• On certain geometric properties of the Yao-Yao graphs
• On geometric spanners of Euclidean and unit disk graphs
• Packing plane spanning graphs with short edges in complete geometric graphs
• Local approximation schemes for topology control
• Bounded-degree plane geometric spanners in practice
• Efficient construction of low weight bounded degree planar spanner
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
• Spanners for geometric intersection graphs with applications
• Computing Lightweight Spanners Locally
• Spanners of Complete k-Partite Geometric Graphs
• ON SPANNERS OF GEOMETRIC GRAPHS
• Improved local algorithms for spanner construction
• On Spanners of Geometric Graphs
• On plane geometric spanners: a survey and open problems
• On bounded degree plane strong geometric spanners
• On the stretch factor of Delaunay triangulations of points in convex position
• Algorithms and Computation
• Light Euclidean Spanners with Steiner Points
• On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
• Spanners for Geometric Intersection Graphs

This page was built for publication: On spanners and lightweight spanners of geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068627)