Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen

For an undirected $n$-vertex planar graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of…