Structured Recursive Separator Decompositions for Planar Graphs in Linear Time

Philip N. Klein, Shay Mozes, and Christian Sommer
STOC 2013 - 45th ACM Symposium on Theory of Computing (pp. 505-514)

Given a planar graph \(G\) on \(n\) vertices and an integer parameter \(r \lt 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(\sqrt 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 exponentially increasing sequence \(\mathbf{r} = (r_1, r_2,\dots)\), our algorithm can produce a recursive \(\mathbf{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).

@inproceedings{KMS13,
 author    = {Philip N. Klein 
              and Shay Mozes 
              and Christian Sommer},
 title     = {Structured Recursive Separator Decompositions 
              for Planar Graphs in Linear Time},
 year      = {2013},
 booktitle = {45th ACM Symposium on Theory of Computing (STOC)},
 pages     = {505--514},
 url       = {http://dx.doi.org/10.1145/2488608.2488672},
 doi       = {10.1145/2488608.2488672},
}

Official version
Local version (322.0 KB)
arXiv

Home → Publications → Structured Recursive Separator Decompositions for Planar Graphs in Linear Time