| Abstract (2008) | |||||||||||||||
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, provided that M ≥ 56r log 2 B. Together with the planar embedding algorithm presented in the companion paper [27], 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 [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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||