On bounded degree plane strong geometric spanners

DOI10.1016/j.jda.2012.03.004zbMath1247.68306OpenAlexW1972171563MaRDI QIDQ450575

Prosenjit Bose, Paz Carmi, Lilach Chaitman-Yerushalmi

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.03.004

zbMATH Keywords

geometric spannerscomputational geometryDelaunay triangulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (11)

On plane geometric spanners: a survey and open problems ⋮ Geometric spanning trees minimizing the Wiener index ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Unnamed Item ⋮ Improved spanning ratio for low degree plane spanners ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Lattice spanners of low degree ⋮ There are plane spanners of degree 4 and moderate stretch factor

Cites Work

• Unnamed Item
• On plane geometric spanners: a survey and open problems
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Improved local algorithms for spanner construction
• Classes of graphs which approximate the complete Euclidean graph
• Approximating geometric bottleneck shortest paths
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• On Spanners and Lightweight Spanners of Geometric Graphs
• Geometric Spanner Networks
• Plane Spanners of Maximum Degree Six
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Improved upper bound on the stretch factor of delaunay triangulations

This page was built for publication: On bounded degree plane strong geometric spanners