O(1)-Distortion Planar Emulators for String Graphs
Published: Oct 24, 2025
Last Updated: Oct 24, 2025
Authors:Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, Da Wei Zheng
Abstract
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$ with $V(H) = V(G)$, such that every pair of vertices $(u,v)$ satisfies $\delta_G(u,v) \le \delta_H(u,v) \le O(1) \cdot \delta_G(u,v).$