A note on optimal degree-three spanners of the square lattice

DOI10.1142/S179383092150124XMaRDI QIDQ5866023

Damien Galant, Cédric Pilatte

Publication date: 10 June 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphstretch factorplane spannerminimum dilation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Related Items (1)

Minimum weight Euclidean \((1+\varepsilon)\)-spanners

Cites Work

• On plane geometric spanners: a survey and open problems
• Constructing plane spanners of bounded degree and low weight
• There are planar graphs almost as good as the complete graph
• There are plane spanners of degree 4 and moderate stretch factor
• Lattice Spanners of Low Degree
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• Towards plane spanners of degree 3
• Degree four plane spanners: Simpler and better
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES

This page was built for publication: A note on optimal degree-three spanners of the square lattice