Cutting Planarians: Planar Emulators for String Graphs

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 𝐺 has an 𝑂 (1)-distortion planar emulator: that is, there exists an edge-weighted planar graph 𝐻 containing every vertex in 𝐺, such that every pair of vertices (𝑢, 𝑣) satisfies 𝛿 𝐺 (𝑢, 𝑣) ≤ 𝛿 𝐻 (𝑢, 𝑣) ≤ 𝑂 (1) • 𝛿 𝐺 (𝑢, 𝑣). Furthermore, we show that for any constant 𝜀 > 0, there is an edge-weighted planar graph 𝐻 ′ such that every pair of vertices (𝑢, 𝑣) satisfies 𝛿 𝐺 (𝑢, 𝑣) ≤ 𝛿 𝐻 ′ (𝑢, 𝑣) ≤ (1 + 𝜀) • 𝛿 𝐺 (𝑢, 𝑣) + 𝑂 (𝜀 -4 poly log 𝑛). 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 + 𝜀, +𝑂 (1)) mixeddistortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive +(𝜀Δ + 𝑂 (1))-distortion embedding of string graphs 𝐺 with diameter Δ into graphs of constant treewidth 𝑂 (𝜀 -4 ).