Quasi-isometries between graphs with variable edge lengths

2025/03/10 by Davies, James, Hatzel, Meike, Hickingbotham, Robert · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2503.07448

Abstract

This paper investigates quasi-isometries between graphs with variable edge lengths. A quasi-isometry is a mapping between metric spaces that approximately preserves distances, allowing for a bounded amount of additive and multiplicative distortion. Recently, Nguyen, Scott, and Seymour conjectured that, by appropriately adjusting the edge lengths of the target graph along with modifying the additive distortion constant, the multiplicative distortion factor could be eliminated. We disprove this conjecture.

Cited by

• String graphs are quasi-isometric to planar graphs

Related

• Quasi-Isometric Graph Simplifications
• Asymptotic structure. II. Path-width and additive quasi-isometry
• Quasi-isometries between non-locally-finite graphs and structure trees
• Quasi-isometry of pairs: surfaces in graph manifolds
• Graphs that are quasi-isometric to graphs with bounded treewidth