---
OA_place: publisher
OA_type: gold
_id: '22246'
abstract:
- lang: eng
  text: "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.\r\nAs 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)."
acknowledgement: "Hsien-Chih Chang and Jonathan Conroy are supported by the U.S.\r\nNational
  Science Foundation CAREER Award under the Grant No.\r\nCCF-2443017."
article_processing_charge: No
arxiv: 1
author:
- first_name: Hsien Chih
  full_name: Chang, Hsien Chih
  last_name: Chang
- first_name: Jonathan
  full_name: Conroy, Jonathan
  last_name: Conroy
- first_name: Zihan
  full_name: Tan, Zihan
  last_name: Tan
- first_name: Da Wei
  full_name: Zheng, Da Wei
  id: af77956b-e859-11ef-8dc9-d301b898e32f
  last_name: Zheng
citation:
  ama: '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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: 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.
conference:
  end_date: 2026-06-26
  location: Salt Lake City, UT, United States
  name: 'STOC: Symposium on the Theory of Computing'
  start_date: 2026-06-22
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:37Z
date_published: 2026-06-09T00:00:00Z
date_updated: 2026-07-06T10:25:23Z
day: '09'
ddc:
- '500'
- '000'
department:
- _id: MoHe
doi: 10.1145/3798129.3800917
external_id:
  arxiv:
  - '2510.21700'
file:
- access_level: open_access
  checksum: c184596a3e18fee912caef4c7751a96d
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-06T10:23:09Z
  date_updated: 2026-07-06T10:23:09Z
  file_id: '22253'
  file_name: 2026_STOC_Chang.pdf
  file_size: 2015699
  relation: main_file
  success: 1
file_date_updated: 2026-07-06T10:23:09Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2140-2151
publication: 58th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9798400725364'
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Cutting planarians: Planar emulators for string graphs'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...