Distance Approximating Minors for Planar and Minor-Free Graphs

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+\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.