We present I/O-optimal algorithms for several fundamental problems on planar graphs. Our main contribution is an I/O-efficient algorithm for computing a small vertex separator of an unweighted planar graph. This algorithm is superior to all existing external memory algorithms for this problem, as it requires neither a breadth-first search tree nor an embedding of the graph as part of the input. In fact, we derive I/O-optimal algorithms for planar embedding, breadth-first search, depth-first search, single source shortest paths, and computing weighted separators of planar graphs from our unweighted separator algorithm.
展开▼
