Carleton University
Technical Report TR-01-02
May 2001
I/O-Efficient Planar Separators and Applications
Norbert Zeh
Abstract
We present a new algorithm to compute a subset S of vertices of a planar graph G whose removal partitions G into O(N/h2) subgraphs of size O(h2) and with boundary size O(h) each. The size of S is O(N/h). Computing S takes O(sort(N)) I/Os and linear space, provided that M>=56h2 log2 B. Together with recent reducibility results, this leads to O(sort(N)) I/O algorithms for breadth-first search (BFS), depth-first search (DFS), and single source shortest paths (SSSP) on undirected embedded planar graphs. Our separator algorithm does not need a BFS tree or an embedding of G to be given as part of the input. Instead we argue that `local embeddings’ of subgraphs of G are enough.