DI-UMONS : Dépôt institutionnel de l’université de Mons
Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2020-11-08 - Divers/Base de données - Anglais - 6 page(s)

Pilatte Cédric , Galant Damien, "A note on optimal degree-three spanners of the square lattice"

  • Codes CREF : Géométrie combinatoire et convexité (DI1118), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Logique mathématique (S838)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Algèbre, Géométrie et Interactions fondamentales (AGIF), Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) In this short note, we prove that the degree-three dilation of the square lattice ℤ^2 is 1+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.

Identifiants :
  • arXiv : 2010.13473
   
20, place du Parc, B7000 Mons - Belgique
Tél +32 (0)65 373111
Courriel: info.mons@umons.ac.be