Paths and Intersections: Exact Emulators for Planar Graphs

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\left(f^{2} k^{2}\right)$ 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\left(k^{2}\right)$ 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\left(k^{4}\right)$ 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.