Cutting Planarians: Planar Emulators for String Graphs

Abstract

In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\epsilon$ distortion regimes. Furthermore, the distance sketches themselves are planar graphs. First, we show that every unweighted string graph $G$ has an $O(1)$-distortion planar emulator: that is, there exists an edge-weighted planar graph $H$ containing every vertex in $G$, such that every pair of vertices $(u,v)$ satisfies $\hat{I}{´}_G(u,v)\le \hat{I}{´}_H(u,v)\le O(1)\cdot \hat{I}{´}_G(u,v)$. Furthermore, we show that for any constant $\epsilon >0$, there is an edge-weighted planar graph $H^{\prime }$ such that every pair of vertices $(u,v)$ satisfies $\hat{I}{´}_G(u,v)\le \hat{I}{´}_{H^{\prime }}(u,v)\le (1+\epsilon )\cdot \hat{I}{´}_G(u,v)+O({\epsilon }^{-4}\text{poly}\log n)$. No previous constructions of sparse distance sketches were known even for intersection graphs of simple shapes like axis-parallel rectangles or fat convex polygons. As applications, we construct the first $(1+\epsilon ,+O(1))$ mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive $+(\epsilon \hat{I}”+O(1))$-distortion embedding of string graphs $G$ with diameter $\hat{I}”$ into graphs of constant treewidth $O({\epsilon }^{-4})$.

full version of STOC 2026 paper