External Memory Algorithms for Outerplanar Graphs

摘要

We present external memory algorihtms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a 2/3-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O(perm(N)) I/Os, as all these problems have linear time solutions in internal memroy. For BFS, DFS, and outerplanar embedding we show matching lower bounds.