---
res:
  bibo_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.\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).@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Hsien Chih
      foaf_name: Chang, Hsien Chih
      foaf_surname: Chang
  - foaf_Person:
      foaf_givenName: Jonathan
      foaf_name: Conroy, Jonathan
      foaf_surname: Conroy
  - foaf_Person:
      foaf_givenName: Zihan
      foaf_name: Tan, Zihan
      foaf_surname: Tan
  - foaf_Person:
      foaf_givenName: Da Wei
      foaf_name: Zheng, Da Wei
      foaf_surname: Zheng
      foaf_workInfoHomepage: http://www.librecat.org/personId=af77956b-e859-11ef-8dc9-d301b898e32f
  bibo_doi: 10.1145/3798129.3800917
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0737-8017
  - http://id.crossref.org/issn/9798400725364
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: 'Cutting planarians: Planar emulators for string graphs@'
...