I/O-optimal algorithms for planar graphs using separators
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 1/0-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.
|Conference||13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002|
Maheshwari, A, & Zeh, N. (Norbert). (2002). I/O-optimal algorithms for planar graphs using separators. Presented at the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002.