  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 exponentially increasing
sequence r = (r_1,r_2,...), 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).
