Cutting Planarians: Planar Emulators for String Graphs
Open Access
- 9 June 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2140-2151
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).Keywords
Funding Information
- National Science Foundation (CCF-2443017)
This publication has 27 references indexed in Scilit:
- The Steiner path aggregation problemInformation Processing Letters, 2025
- On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs2020
- Plane hop spanners for unit disk graphs: Simpler and betterComputational Geometry, 2020
- Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed MinorAlgorithmica, 2013
- Compact and low delay routing labeling scheme for Unit Disk GraphsComputational Geometry, 2012
- Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar GraphsDiscrete & Computational Geometry, 2011
- Planar Hop Spanners for Unit Disk GraphsLecture Notes in Computer Science, 2010
- Spiraling and Folding: The Word ViewAlgorithmica, 2009
- Recognizing string graphs in NPJournal of Computer and System Sciences, 2003
- String graphs requiring exponential representationsJournal of Combinatorial Theory, Series B, 1991