Partitioning planar graphs with costs and weights.

摘要

A good separator leads to good partitioning. A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. In particular, we consider connected planar graphs with costs and weights on vertices, where weights are used to estimate the sizes of the components and costs are used to estimate the quatility of the separator. In this thesis, we describe a new algorithm for computing vertex separators in planar graphs. Also, we introduce a tuning technique that results in considerable reduction of the cost of the produced separators. As an application, we design an algorithm to construct an edge separator. More importantly, we show new theorems of vertex and edge separators that have theoretically guaranteed upper bounds both on the quality of the partitions and on the time needed to find them. We show that our partitioning algorithms are efficient, effective, and easy to implement.