A simple approach for lower-bounding the distortion in any Hyperbolic embedding

David Coudert 1 Guillaume Ducoffe 1, 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We answer open questions of [Verbeek and Suri, SOCG'14] on the relationships between Gromov hyperbolicity and the optimal stretch of graph embeddings in Hyperbolic space. Then, based on the relationships between hyperbolicity and Cops and Robber games, we turn necessary conditions for a graph to be Cop-win into sufficient conditions for a graph to have a large hyperbolicity (and so, no low-stretch embedding in Hyperbolic space). In doing so we derive lower-bounds on the hyperbolicity in various graph classes – such as Cayley graphs, distance-regular graphs and generalized polygons, to name a few. It partly fills in a gap in the literature on Gromov hyperbolicity, for which few lower-bound techniques are known.
Type de document :
Communication dans un congrès
EUROCOMB'17 -- The European Conference on Combinatorics, Graph Theory and Applications, Aug 2017, Vienna, Austria. Elsevier, Electronic Notes in Discrete Mathematics, 61, pp.293 - 299, 2017, <10.1016/j.endm.2017.06.051>
Liste complète des métadonnées


https://hal.inria.fr/hal-01573042
Contributeur : David Coudert <>
Soumis le : mardi 8 août 2017 - 12:07:23
Dernière modification le : mercredi 9 août 2017 - 01:08:19

Fichier

CouDuc--EUROCOMB17.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Guillaume Ducoffe. A simple approach for lower-bounding the distortion in any Hyperbolic embedding. EUROCOMB'17 -- The European Conference on Combinatorics, Graph Theory and Applications, Aug 2017, Vienna, Austria. Elsevier, Electronic Notes in Discrete Mathematics, 61, pp.293 - 299, 2017, <10.1016/j.endm.2017.06.051>. <hal-01573042>

Partager

Métriques

Consultations de
la notice

154

Téléchargements du document

18