[{"external_id":{"arxiv":["2411.09182"]},"volume":367,"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"22003","file_date_updated":"2026-06-22T08:43:47Z","year":"2026","language":[{"iso":"eng"}],"publication":"42nd International Symposium on Computational Geometry","corr_author":"1","title":"Lower bounding the Gromov–Hausdorff distance in metric graphs","day":"27","publication_status":"published","ddc":["500"],"type":"conference","abstract":[{"lang":"eng","text":"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."}],"article_number":"3:1-3:16","publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"das_tickbox":"0","doi":"10.4230/LIPIcs.SoCG.2026.3","conference":{"end_date":"2026-06-05","start_date":"2026-06-02","location":"New Brunswick, NJ, United States","name":"SoCG: Symposium on Computational Geometry"},"date_updated":"2026-06-22T08:49:17Z","citation":{"ieee":"H. Adams, S. Majhi, F. Manin, Z. Virk, and N. Zava, “Lower bounding the Gromov–Hausdorff distance in metric graphs,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ista":"Adams H, Majhi S, Manin F, Virk Z, Zava N. 2026. Lower bounding the Gromov–Hausdorff distance in metric graphs. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 3:1-3:16.","chicago":"Adams, Henry, Sushovan Majhi, Fedor Manin, Ziga Virk, and Nicolò Zava. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>.","short":"H. Adams, S. Majhi, F. Manin, Z. Virk, N. Zava, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"Adams H, Majhi S, Manin F, Virk Z, Zava N. Lower bounding the Gromov–Hausdorff distance in metric graphs. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>","apa":"Adams, H., Majhi, S., Manin, F., Virk, Z., &#38; Zava, N. (2026). Lower bounding the Gromov–Hausdorff distance in metric graphs. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>","mla":"Adams, Henry, et al. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>."},"intvolume":"       367","has_accepted_license":"1","month":"05","quality_controlled":"1","OA_type":"gold","OA_place":"publisher","oa_version":"Published Version","arxiv":1,"department":[{"_id":"HeEd"}],"keyword":["Gromov–Hausdorff distance","distortion","connectedness","Borsuk–Ulam theorem"],"article_processing_charge":"Yes","file":[{"file_size":1091310,"success":1,"date_updated":"2026-06-22T08:43:47Z","content_type":"application/pdf","creator":"dernst","file_name":"2026_LIPIcSSoCG_Adams.pdf","file_id":"22115","relation":"main_file","checksum":"25d27c016409563196b8aecfe5bfdf41","access_level":"open_access","date_created":"2026-06-22T08:43:47Z"}],"oa":1,"date_created":"2026-06-14T22:01:44Z","license":"https://creativecommons.org/licenses/by/4.0/","status":"public","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.3","date_published":"2026-05-27T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Henry","last_name":"Adams","full_name":"Adams, Henry"},{"first_name":"Sushovan","full_name":"Majhi, Sushovan","last_name":"Majhi"},{"full_name":"Manin, Fedor","last_name":"Manin","first_name":"Fedor"},{"first_name":"Ziga","full_name":"Virk, Ziga","last_name":"Virk","id":"2E36B656-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-8686-1888","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad","last_name":"Zava","full_name":"Zava, Nicolò","first_name":"Nicolò"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"project":[{"name":"Algebraic Footprints of Geometric Features in Homology","call_identifier":"FWF","grant_number":"I04245","_id":"26AD5D90-B435-11E9-9278-68D0E5697425"}],"scopus_import":"1","acknowledgement":"Funding Henry Adams: Simons Foundation Travel Support for Mathematicians.\r\nŽiga Virk: Slovene research agency grant P1-0292.\r\nNicolò Zava: FWF Grant, Project number I4245-N35.\r\n"}]