STOC2022
Almost-linear ε-emulators for planar graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
2 citations
Abstract
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+ε.