{"ID":2868247,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.17226","arxiv_id":"2509.17226","title":"Distance Approximating Minors for Planar and Minor-Free Graphs","abstract":"Given an edge-weighted graph $G$ and a subset of vertices $T$ called terminals, an $α$-distance-approximating minor ($α$-DAM) of $G$ is a graph minor $H$ of $G$ that contains all terminals, such that the distance between every pair of terminals is preserved up to a factor of $α$. Distance-approximating minor would be an effective distance-sketching structure on minor-closed family of graphs; in the constant-stretch regime it generalizes the well-known Steiner Point Removal problem by allowing the existence of (a small number of) non-terminal vertices. Unfortunately, in the $(1+\\varepsilon)$ regime the only known DAM construction for planar graphs relies on overlaying $\\tilde{O}_\\varepsilon(|T|)$ shortest paths in $G$, which naturally leads to a quadratic bound in the number of terminals [Cheung, Goranci, and Henzinger, ICALP 2016]. We break the quadratic barrier and build the first $(1+\\varepsilon)$-distance-approximating minor for $k$-terminal planar graphs and minor-free graphs of near-linear size $\\tilde{O}_\\varepsilon(k)$. In addition to the near-optimality in size, the construction relies only on the existence of shortest-path separators [Abraham and Gavoille, PODC 2006] and $\\varepsilon$-covers [Thorup, J.\\ ACM 2004]. Consequently, this provides an alternative and simpler construction to the near-linear-size emulator for planar graphs [Chang, Krauthgamer, and Tan, STOC 2022], as well as the first near-linear-size emulator for minor-free graphs. Our DAM can be constructed in near-linear time.","short_abstract":"Given an edge-weighted graph $G$ and a subset of vertices $T$ called terminals, an $α$-distance-approximating minor ($α$-DAM) of $G$ is a graph minor $H$ of $G$ that contains all terminals, such that the distance between every pair of terminals is preserved up to a factor of $α$. Distance-approximating minor would be a...","url_abs":"https://arxiv.org/abs/2509.17226","url_pdf":"https://arxiv.org/pdf/2509.17226v1","authors":"[\"Hsien-Chih Chang\",\"Jonathan Conroy\"]","published":"2025-09-21T20:15:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\",\"cs.DM\"]","methods":"[]","has_code":false}