A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up the implementation of graph partitioning algorithms and improve the partition quality. In particular, we consider planar graphs with costs and weights on the vertices, where weights are used to estimate the sizes of the partitions and costs are used to estimate the size of the separator. We show that in these graphs one can always find a small cost separator (consisting of vertices or edges) that partitions the graph into components of bounded weight. We describe implementations of the partitioning algorithms and discuss results of our experiments.

Algorithms, Design, G2.2 [Graph Theory]: Graph algorithms - Mathematics of computation, Graph algorithms, Graph partitioning algorithms, Graph separators, Implementation, Performance
dx.doi.org/10.1145/1187436.1210588
Journal of Experimental Algorithmics
Computational Geometry Lab

Aleksandrov, L. (Lyudmil), Djidjev, H. (Hristo), Guo, H. (Hua), & Maheshwari, A. (2006). Partitioning planar graphs with costs and weights. Journal of Experimental Algorithmics, 11. doi:10.1145/1187436.1210588