In this paper, we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane, known as string graphs, in the constant and $1+\varepsilon$ distortion regimes. Furthermore, the distance sketches themselves are planar graphs.
First, we demonstrate that every unweighted string graph $G$ has an $O(1)$-distortion planar emulator: there exists an edge-weighted planar graph $H$ containing every vertex in $G$, such that every pair of vertices $(u,v)$ satisfies $\delta_G(u,v) \leq \delta_H(u,v) \leq O(1) \times \delta_G(u,v)$.
Additionally, we show that for any constant $\varepsilon > 0$, there is an edge-weighted planar graph $H'$ such that every pair of vertices $(u,v)$ satisfies $\delta_G(u,v) \leq \delta_{H'}(u,v) \leq (1+\varepsilon) \times \delta_G(u,v) + O(\varepsilon^{-4} \operatorname{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+\varepsilon, +O(1))$ mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive $+(\varepsilon \Delta + O(1))$-distortion embedding of string graphs $G$ with diameter $\Delta$ into graphs of constant treewidth $O(\varepsilon^{-4})$.
Blogger's Review: This paper represents a significant advancement in the study of string graphs, providing effective planar emulators that overcome previous limitations in sparse distance sketch constructions. This work not only holds theoretical significance but also offers new insights for practical applications, particularly in graph embedding and covering problems.