An exponential lower bound for cut sparsifiers in planar graphs

Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz

Given an edge-weighted graph $G$ with a set $Q$ of $k$ terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts bet…