Abstract. We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph G with N vertices and an integer r > 0, a vertex separator of size O(N/ √ r) that partitions G into O(N/r) subgraphs of size at most r and boundary size O( √ r) can be computed in O(sort(N )) I/Os. This bound holds provided that M ≥ 56r log 2 B. Together with an I/O-efficient planar embedding algorithm presented in [33] , this result is the basis for I/O-efficient solutions to many other fundamental problems on planar graphs, including breadth-first search and shortest paths [5, 8] , depth-first search [6, 9] , strong connectivity [9] , and topological sorting [7, 8] . Our second result shows that, given I/O-efficient solutions to these problems, a general separator algorithm for graphs with costs and weights on their vertices [3] can be made I/O-efficient. Many classical separator theorems are special cases of this result. In particular, our I/O-efficient version allows the computation of a separator as produced by our first separator algorithm, but without placing any constraints on r in relation to the memory size.
Maheshwari and Zeh REF showed that such a partition of a planar graph can be computed I/O-efficiently with O(sort(V )) I/Os provided that M min(cB 2 , cR log 2 B), for a sufficiently big constant c. All I/O-efficient planar graph algorithms first compute a partition of the graph with R = Θ(B 2 ) and use it to reduce the original problem to a smaller problem, defined on the Θ(V /B) separator vertices.
I/O-efficient planar separators
SIAM Journal on Computing
Mathematics Computer Science