{"ID":2895227,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09620","arxiv_id":"2507.09620","title":"Paths and Intersections: Exact Emulators for Planar Graphs","abstract":"We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$). Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.","short_abstract":"We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact...","url_abs":"https://arxiv.org/abs/2507.09620","url_pdf":"https://arxiv.org/pdf/2507.09620v1","authors":"[\"George Z. Li\",\"Zihan Tan\",\"Tianyi Zhang\"]","published":"2025-07-13T12:58:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}