@inproceedings{22246,
  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+ε 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).},
  author       = {Chang, Hsien Chih and Conroy, Jonathan and Tan, Zihan and Zheng, Da Wei},
  booktitle    = {58th Annual ACM Symposium on Theory of Computing},
  isbn         = {9798400725364},
  issn         = {0737-8017},
  location     = {Salt Lake City, UT, United States},
  pages        = {2140--2151},
  publisher    = {Association for Computing Machinery},
  title        = {{Cutting planarians: Planar emulators for string graphs}},
  doi          = {10.1145/3798129.3800917},
  year         = {2026},
}