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 $\alpha$-distance-approximating minor ($\alpha$-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 $\alpha$. 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+\epsilon )$ regime the only known DAM construction for planar graphs relies on overlaying ${\tilde{O}}_{\epsilon }(|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+\epsilon )$-distance-approximating minor for $k$-terminal planar graphs and minor-free graphs of near-linear size ${\tilde{O}}_{\epsilon }(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 $\epsilon$-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.

arXiv comment32 pages, 6 figures. Accepted to FOCS 2025