Almost-linear ε-emulators for planar graphs

We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph 𝐺 (with edge weights) and a subset of 𝑘 terminal vertices, the goal is to construct an 𝜀-emulator, which is a small planar graph 𝐺 ′ that contains the terminals and preserves the distances between the terminals up to factor 1 + 𝜀.

We design the first 𝜀-emulators for planar graphs of almost-linear size 𝑘 1+𝑜 (1) /poly 𝜀. In terms of 𝑘, this is a dramatic improvement over the previous quadratic upper bound of Cheung, Goranci and Henzinger [ICALP 2016], and breaks below known quadratic lower bounds for exact emulators (the case when 𝜀 = 0). Moreover, our emulators can be computed in near-linear time, with applications to fast (1 + 𝜀)-approximation algorithms for basic optimization problems on planar graphs such as minimum (𝑠, 𝑡)-cut and diameter.

• Theory of computation → Graph algorithms analysis; Random projections and metric embeddings.