2025/10/24 by Hsien-Chih Chang, Jonathan Conroy, Chang, Hsien-Chih +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2510.21700
openalex publication_date 2025/10/24 · openalex created_date 2025/10/28 · openalex updated_date 2026/07/28
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(ε-4\textrmpolylog n). 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).