There are plane spanners of degree 4 and moderate stretch factor

DOI10.1007/s00454-015-9676-zzbMath1314.05132arXiv1403.5350OpenAlexW2081341653MaRDI QIDQ2349855

Nicolas Bonichon, Ljubomir Perković, Ge Xia, Iyad A. Kanj

Publication date: 18 June 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.5350

zbMATH Keywords

Delaunay triangulationbounded degreestretch factorplane spanner

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (11)

Improved bounds on the stretch factor of \(Y_{4}\) ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Cone-based spanners of constant degree ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Bounded-degree spanners in the presence of polygonal obstacle ⋮ On plane constrained bounded-degree spanners ⋮ Improved spanning ratio for low degree plane spanners ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lattice spanners of low degree ⋮ A note on optimal degree-three spanners of the square lattice

Cites Work

• Unnamed Item
• On plane geometric spanners: a survey and open problems
• On bounded degree plane strong geometric spanners
• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• Classes of graphs which approximate the complete Euclidean graph
• Euclidean spanner graphs with degree four
• On plane constrained bounded-degree spanners
• There are planar graphs almost as good as the complete graph
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• The Stretch Factor of L 1- and L  ∞ -Delaunay Triangulations
• Plane Spanners of Maximum Degree Six
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• π/2-ANGLE YAO GRAPHS ARE SPANNERS
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Routing with guaranteed delivery in ad hoc wireless networks

This page was built for publication: There are plane spanners of degree 4 and moderate stretch factor