TR-176: Edge Separators of Planar and Outerplanar Graphs with Applications

Abstract

We consider the problem of finding a small set of edges whose removal divides a given graph into roughly equal parts. We show that every planar graph with nvertices and a maximal degree k has an O()-edge separator, which bound is asymptotically optimal. This improves the previously best known upper bound of 0(k In). We prove that the bisection width of the class of planar graphs and trees of n vertices and degree k is 0( and 0(k log nllog k) respectively, both optimal within a constant factor. All proofs are constructive and yield optimal O(n) algorithms. The separator theorems are applied to embed efficiently planar and outerplanar graphs into binary trees, hypercubes, butterfly graphs, CCC graphs, shuffle-exchange graphs, de Brujn graphs, and d-dimensional meshes. The embeddings are shown to be optimal or almost optimal with respect to the average dilation and the expansion of the embedding.