On bounded degree plane strong geometric spanners

DOI10.1016/J.JDA.2012.03.004MaRDI QIDQ450575zbMATH OpenOpenAlexFDO

Authors 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

computational geometryDelaunay triangulationgeometric spanners

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)

Recommendations

• Degree four plane spanners: simpler and better
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• scientific article; zbMATH DE number 1947396
• Degree four plane spanners: simpler and better
• Constructing plane spanners of bounded degree and low weight

Cites work

• scientific article; zbMATH DE number 1947396 (Why is no real title available?)
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Approximating geometric bottleneck shortest paths
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Classes of graphs which approximate the complete Euclidean graph
• Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Geometric Spanner Networks
• Improved local algorithms for spanner construction
• Improved upper bound on the stretch factor of Delaunay triangulations
• On plane geometric spanners: a survey and open problems
• On spanners and lightweight spanners of geometric graphs
• Plane Spanners of Maximum Degree Six

Cited in

(16)

• Lower bounds on the dilation of plane spanners
• There are plane spanners of degree 4 and moderate stretch factor
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Geometric spanning trees minimizing the Wiener index
• Bounded-degree plane geometric spanners in practice
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• scientific article; zbMATH DE number 1947396 (Why is no real title available?)
• Lattice spanners of low degree
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Lattice spanners of low degree
• Diamond Triangulations Contain Spanners of Bounded Degree
• Lower bounds on the dilation of plane spanners
• There are Plane Spanners of Maximum Degree 4
• On plane geometric spanners: a survey and open problems
• Constructing plane spanners of bounded degree and low weight
• Geometric spanning trees minimizing the Wiener index

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

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