External memory algorithms for outerplanar graphsPublic Deposited
Downloadable ContentDownload PDF
- Resource Type
We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a2-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 memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
- Maheshwari, A, & Zeh, N. (Norbert). (1999). External memory algorithms for outerplanar graphs. doi:10.1007/3-540-46632-0_31
- Date Created
- In Collection: