[{"date_created":"2026-06-14T22:01:44Z","oa":1,"file":[{"file_id":"22115","file_name":"2026_LIPIcSSoCG_Adams.pdf","checksum":"25d27c016409563196b8aecfe5bfdf41","relation":"main_file","date_created":"2026-06-22T08:43:47Z","access_level":"open_access","file_size":1091310,"date_updated":"2026-06-22T08:43:47Z","success":1,"content_type":"application/pdf","creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2026-05-27T00:00:00Z","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.3","status":"public","license":"https://creativecommons.org/licenses/by/4.0/","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","scopus_import":"1","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":[{"grant_number":"I04245","_id":"26AD5D90-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algebraic Footprints of Geometric Features in Homology"}],"author":[{"full_name":"Adams, Henry","last_name":"Adams","first_name":"Henry"},{"last_name":"Majhi","full_name":"Majhi, Sushovan","first_name":"Sushovan"},{"full_name":"Manin, Fedor","last_name":"Manin","first_name":"Fedor"},{"full_name":"Virk, Ziga","last_name":"Virk","first_name":"Ziga","id":"2E36B656-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Zava, Nicolò","last_name":"Zava","first_name":"Nicolò","orcid":"0000-0001-8686-1888","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad"}],"has_accepted_license":"1","month":"05","department":[{"_id":"HeEd"}],"oa_version":"Published Version","arxiv":1,"quality_controlled":"1","OA_type":"gold","OA_place":"publisher","article_processing_charge":"Yes","keyword":["Gromov–Hausdorff distance","distortion","connectedness","Borsuk–Ulam theorem"],"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."}],"das_tickbox":"0","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"article_number":"3:1-3:16","date_updated":"2026-06-22T08:49:17Z","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"},"intvolume":"       367","citation":{"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>.","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>","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>","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.","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>.","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."},"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":367,"external_id":{"arxiv":["2411.09182"]},"title":"Lower bounding the Gromov–Hausdorff distance in metric graphs","corr_author":"1","publication":"42nd International Symposium on Computational Geometry","language":[{"iso":"eng"}],"year":"2026","_id":"22003","file_date_updated":"2026-06-22T08:43:47Z","publication_status":"published","day":"27","type":"conference","ddc":["500"]},{"das_tickbox":"0","article_number":"94:1-94:18","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774451"]},"abstract":[{"lang":"eng","text":"Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs."}],"citation":{"apa":"Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., &#38; Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>","mla":"Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point Effect.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 94:1-94:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>.","ieee":"S. Bhore <i>et al.</i>, “DAG covers for structured graphs: The Steiner point effect,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","chicago":"Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner Point Effect.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>.","ista":"Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG covers for structured graphs: The Steiner point effect. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.","short":"S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The Steiner point effect. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>"},"intvolume":"       388","date_updated":"2026-09-17T10:27:46Z","conference":{"start_date":"2026-08-31","end_date":"2026-09-04","name":"ESA: European Symposium on Algorithms","location":"L’Aquila, Italy"},"doi":"10.4230/LIPIcs.ESA.2026.94","researchdata_availability":"no","publication":"34th Annual European Symposium on Algorithms","title":"DAG covers for structured graphs: The Steiner point effect","corr_author":"1","_id":"22918","year":"2026","file_date_updated":"2026-09-17T10:09:22Z","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"external_id":{"arxiv":["2604.04186"]},"volume":388,"type":"conference","ddc":["000"],"publication_status":"published","day":"25","date_created":"2026-09-13T22:01:53Z","oa":1,"file":[{"checksum":"2082683b3b72865c6a795305e5d61276","relation":"main_file","access_level":"open_access","date_created":"2026-09-17T10:09:22Z","file_name":"2026_LIPIcsESA_Bhore.pdf","file_id":"22948","content_type":"application/pdf","creator":"dernst","file_size":1123327,"success":1,"date_updated":"2026-09-17T10:09:22Z"}],"acknowledgement":"This work was initiated at Dagstuhl Seminar 25212: Metric Sketching and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser: This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.","author":[{"first_name":"Sujoy","full_name":"Bhore, Sujoy","last_name":"Bhore"},{"last_name":"Chang","full_name":"Chang, Hsien Chih","first_name":"Hsien Chih"},{"first_name":"Jonathan","full_name":"Conroy, Jonathan","last_name":"Conroy"},{"first_name":"Arnold","full_name":"Filtser, Arnold","last_name":"Filtser"},{"first_name":"Eunjin","full_name":"Oh, Eunjin","last_name":"Oh"},{"first_name":"Nicole","full_name":"Wein, Nicole","last_name":"Wein"},{"full_name":"Zheng, Da Wei","last_name":"Zheng","first_name":"Da Wei","id":"af77956b-e859-11ef-8dc9-d301b898e32f"}],"project":[{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"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)"},"scopus_import":"1","date_published":"2026-08-25T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.94","month":"08","has_accepted_license":"1","keyword":["Directed graphs","DAG (directed acyclic graphs)","distortion","metric embeddings","planar graph","treewidth"],"article_processing_charge":"Yes","supplementarymaterial":"yes","quality_controlled":"1","OA_type":"gold","OA_place":"publisher","department":[{"_id":"MoHe"}],"oa_version":"Published Version","arxiv":1}]