---
OA_place: publisher
OA_type: gold
_id: '22003'
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.'
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"
alternative_title:
- LIPIcs
article_number: 3:1-3:16
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Henry
  full_name: Adams, Henry
  last_name: Adams
- first_name: Sushovan
  full_name: Majhi, Sushovan
  last_name: Majhi
- first_name: Fedor
  full_name: Manin, Fedor
  last_name: Manin
- first_name: Ziga
  full_name: Virk, Ziga
  id: 2E36B656-F248-11E8-B48F-1D18A9856A87
  last_name: Virk
- first_name: Nicolò
  full_name: Zava, Nicolò
  id: c8b3499c-7a77-11eb-b046-aa368cbbf2ad
  last_name: Zava
  orcid: 0000-0001-8686-1888
citation:
  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>'
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2026-06-05
  location: New Brunswick, NJ, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2026-06-02
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-14T22:01:44Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T08:49:17Z
day: '27'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.SoCG.2026.3
external_id:
  arxiv:
  - '2411.09182'
file:
- access_level: open_access
  checksum: 25d27c016409563196b8aecfe5bfdf41
  content_type: application/pdf
  creator: dernst
  date_created: 2026-06-22T08:43:47Z
  date_updated: 2026-06-22T08:43:47Z
  file_id: '22115'
  file_name: 2026_LIPIcSSoCG_Adams.pdf
  file_size: 1091310
  relation: main_file
  success: 1
file_date_updated: 2026-06-22T08:43:47Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.3
has_accepted_license: '1'
intvolume: '       367'
keyword:
- Gromov–Hausdorff distance
- distortion
- connectedness
- Borsuk–Ulam theorem
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 26AD5D90-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: I04245
  name: Algebraic Footprints of Geometric Features in Homology
publication: 42nd International Symposium on Computational Geometry
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959774185'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounding the Gromov–Hausdorff distance in metric graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 367
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22918'
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."
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."
alternative_title:
- LIPIcs
article_number: 94:1-94:18
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sujoy
  full_name: Bhore, Sujoy
  last_name: Bhore
- first_name: Hsien Chih
  full_name: Chang, Hsien Chih
  last_name: Chang
- 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
- first_name: Da Wei
  full_name: Zheng, Da Wei
  id: af77956b-e859-11ef-8dc9-d301b898e32f
  last_name: Zheng
citation:
  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>'
  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>'
  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>.'
  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.'
  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.'
  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>.'
  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.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:27:46Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.94
external_id:
  arxiv:
  - '2604.04186'
file:
- access_level: open_access
  checksum: 2082683b3b72865c6a795305e5d61276
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-17T10:09:22Z
  date_updated: 2026-09-17T10:09:22Z
  file_id: '22948'
  file_name: 2026_LIPIcsESA_Bhore.pdf
  file_size: 1123327
  relation: main_file
  success: 1
file_date_updated: 2026-09-17T10:09:22Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.94
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Directed graphs
- DAG (directed acyclic graphs)
- distortion
- metric embeddings
- planar graph
- treewidth
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: 'DAG covers for structured graphs: The Steiner point effect'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...