Structured Recursive Separator Decompositions for Planar Graphs in Linear Time

Given a planar graph G on n vertices and an integer parameter r < n, an r–division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O( r). We provide a linear-time algorithm for computing r–divisions with few holes. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r–divisions for essentially all values of r. In particular, given an increasing sequence r = (r1, r2,...), our algorithm can produce a recursive r–division with few holes in linear time. r–divisions with few holes have been used in efficient algorithms to compute shortest paths, minimum cuts, and maximum flows. Our linear-time algorithm improves upon the decomposition algorithm used in the state-of-the-art algorithm for minimum st–cut (Italiano, Nussbaum, Sankowski, and Wulff-Nilsen, STOC 2011), removing one of the bottlenecks in the overall running time of their algorithm (analogously for minimum cut in planar and bounded-genus graphs)