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

DOI10.1142/S179383092150124XMaRDI QIDQ5866023zbMATH OpenFDO

Authors 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 graphminimum dilationplane spannerstretch factor

Mathematics Subject Classification ID

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

Recommendations

• Lattice spanners of low degree
• Lattice spanners of low degree
• Lower bounds on the dilation of plane spanners
• Lower bounds on the dilation of plane spanners
• Towards plane spanners of degree 3

Cites work

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

Cited in

(1)

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

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

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