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

preprint2021arXivOpen access

Abstract

In this short note, we prove that the degree-three dilation of the square lattice Z2\mathbb{Z}^2 is 1+21+\sqrt{2}. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.