Running summarizing tools on a new article

Abstract: 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(\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 increasing sequence ${\bm r} = (r_1,r_2,...)$, our algorithm can produce a recursive ${\bm r}$--division with few holes in linear time. Such decompositions 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).