Cutting planarians: Planar emulators for string graphs Chang, Hsien Chih Conroy, Jonathan Tan, Zihan Zheng, Da Wei ddc:500 ddc:000 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). Association for Computing Machinery 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/22246 https://research-explorer.ista.ac.at/download/22246/22253 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3798129.3800917 info:eu-repo/semantics/altIdentifier/issn/0737-8017 info:eu-repo/semantics/altIdentifier/isbn/9798400725364 info:eu-repo/semantics/altIdentifier/arxiv/2510.21700 info:eu-repo/semantics/openAccess