Almost-linear ε -emulators for planar graphs

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+ε.

Authors

• Hsien-Chih Chang
• Robert Krauthgamer
• Zihan Tan

Keywords

• Okamura-Seymour instance
• slicing
• spread reduction
• planar metric
• emulator