Structured Recursive Separator Decompositions for Planar Graphs in Linear Time

Philip N. Klein, Shay Mozes, Christian Sommer

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 re…