Partitioning Planar Graphs with Vertex Costs: Algorithms and Applications

We prove separator theorems in which the size of the separator is minimized with respect to non‐negative vertex costs. We show that for any planar graph G there exists a vertex separator of total sum of vertex costs at most $c\sqrt{{\sum }_{v\in V(G)}(\mathrm{cost}(v){)}^2}$ and that this bound is optimal to within a constant factor. Moreover, such a separator can be found in linear time. This theorem implies a variety of other separation results. We describe applications of our separator theorems to graph embedding problems, to graph pebbling, and to multicommodity flow problems.