Exact Emulators for Planar Graphs

We study vertex sparsification for preserving distances in planar graphs: Given an edge-weighted planar graph a subset of $k$ terminal vertices, the goal is to construct an emulator, which is a small edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct an exact planar emulator of size $O(f^2k^2)$ in the setting where the terminals of the input graph lie on $f$ faces in its planar embedding. This generalizes and interpolates between the results of \citet{ChangO20} and \citet{DBLP:journals/siamdm/GoranciHP20}, which obtained an $O(k^2)$ bound in the case where all terminals lie on a single face (i.e., $f=1$), and the folklore $O(k^4)$ bound (see e.g., \cite{krauthgamer2014preserving}) which even holds for general graphs.