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

DOI10.1016/j.endm.2017.06.051zbMath1378.05133OpenAlexW2742412507MaRDI QIDQ1689928

Guillaume Ducoffe, David Coudert

Publication date: 18 January 2018

Full work available at URL: https://hal.inria.fr/hal-01573042/file/CouDuc--EUROCOMB17.pdf

zbMATH Keywords

hyperbolic spaceGromov hyperbolicitycop and robber games

Mathematics Subject Classification ID

Applications of graph theory (05C90) Games involving graphs (91A43) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Limitations on realistic hyperbolic graph drawing

Cites Work

• Unnamed Item
• Unnamed Item
• Data center interconnection networks are not hyperbolic
• On the hyperbolicity of bipartite graphs and intersection graphs
• Metric embedding, hyperbolic space, and social networks
• Hyperbolicity and chordality of a graph
• Characterizing \((\ell ,m)\)-walk-regular graphs
• A game of cops and robbers
• Distance degree regular graphs
• Distance-regularised graphs are distance-regular or distance-biregular
• On Computing the Hyperbolicity of Real-World Graphs
• Cop and Robber Game and Hyperbolicity