conference paper published yes Hsien Chih Chang author Jonathan Conroy author Zihan Tan author Da Wei Zheng author af77956b-e859-11ef-8dc9-d301b898e32f MoHe department STOC: Symposium on the Theory of Computing 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+ε 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 δG(u,v) ≤ δH(u,v) ≤ O(1) · δG(u,v). Furthermore, we show that for any constant ε > 0, there is an edge-weighted planar graph H′ such that every pair of vertices (u,v) satisfies δG(u,v) ≤ δH′(u,v) ≤ (1+ε) · δG(u,v) + O(ε−4polylogn). 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+ε, +O(1)) mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive +(εΔ+O(1))-distortion embedding of string graphs G with diameter Δ into graphs of constant treewidth O(ε−4). https://research-explorer.ista.ac.at/download/22246/22253/2026_STOC_Chang.pdf application/pdfno Association for Computing Machinery2026Salt Lake City, UT, United States eng 0737-8017 9798400725364 2510.2170010.1145/3798129.3800917 2140-2151 Chang HC, Conroy J, Tan Z, Zheng DW. 2026. Cutting planarians: Planar emulators for string graphs. 58th Annual ACM Symposium on Theory of Computing. STOC: Symposium on the Theory of Computing, 2140–2151. Chang, Hsien Chih, Jonathan Conroy, Zihan Tan, and Da Wei Zheng. “Cutting Planarians: Planar Emulators for String Graphs.” In <i>58th Annual ACM Symposium on Theory of Computing</i>, 2140–51. Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3798129.3800917">https://doi.org/10.1145/3798129.3800917</a>. H.C. Chang, J. Conroy, Z. Tan, D.W. Zheng, in:, 58th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2026, pp. 2140–2151. Chang, H. C., Conroy, J., Tan, Z., &#38; Zheng, D. W. (2026). Cutting planarians: Planar emulators for string graphs. In <i>58th Annual ACM Symposium on Theory of Computing</i> (pp. 2140–2151). Salt Lake City, UT, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/3798129.3800917">https://doi.org/10.1145/3798129.3800917</a> Chang, Hsien Chih, et al. “Cutting Planarians: Planar Emulators for String Graphs.” <i>58th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2026, pp. 2140–51, doi:<a href="https://doi.org/10.1145/3798129.3800917">10.1145/3798129.3800917</a>. H. C. Chang, J. Conroy, Z. Tan, and D. W. Zheng, “Cutting planarians: Planar emulators for string graphs,” in <i>58th Annual ACM Symposium on Theory of Computing</i>, Salt Lake City, UT, United States, 2026, pp. 2140–2151. Chang HC, Conroy J, Tan Z, Zheng DW. Cutting planarians: Planar emulators for string graphs. In: <i>58th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2026:2140-2151. doi:<a href="https://doi.org/10.1145/3798129.3800917">10.1145/3798129.3800917</a> 222462026-07-05T22:01:37Z2026-07-06T10:25:23Z