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 gra ph G there exists a vertex separator of total sum of vertex costs at most c root Sigma(nu is an element of V(G))(cost(nu))(2) and that this bound is o ptimal 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 pro blems, to graph pebbling, and to multicommodity flow problems.