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

HomePublications → Structured Recursive Separator Decompositions for Planar Graphs in Linear Time