2026-07-20T14:23:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25809 2026-06-23T12:58:47Z ddc:004 open_access

Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs Adams, Henry Majhi, Sushovan Manin, Fedor Virk, Žiga Zava, Nicolò Gromov-Hausdorff distance distortion connectedness Borsuk-Ulam theorem Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henry Adams and Sushovan Majhi and Fedor Manin and Žiga Virk and Nicolò Zava 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.3 urn:nbn:de:0030-drops-258099 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode