Near-Linear ε-Emulators for Planar Graphs
share
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to construct an ε-emulator, which is a small planar graph G' that contains the terminals and preserves the distances between the terminals up to factor 1+ε. We construct the first ε-emulators for planar graphs of near-linear size Õ(k/ε^O(1)). In terms of k, this is a dramatic improvement over the previous quadratic upper bound of Cheung, Goranci and Henzinger, and breaks below known quadratic lower bounds for exact emulators (the case when ε=0). Moreover, our emulators can be computed in (near-)linear time, which lead to fast (1+ε)-approximation algorithms for basic optimization problems on planar graphs, including multiple-source shortest paths, minimum (s,t)-cut, graph diameter, and dynamic distace oracle.
READ FULL TEXT