Improved Guarantees for Vertex Sparsification in Planar Graphs
Improved Guarantees for Vertex Sparsification in Planar Graphs
Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study vertex sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. We focus on the following notions: (1) Given a digraph $G=(V,E)$ and terminal vertices …