External memory algorithms for outerplanar graphs
Public Deposited- Resource Type
- Creator
- Abstract
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.
- Language
- Publisher
- Identifier
- Citation
- Maheshwari, A, & Zeh, N. (Norbert). (1999). External memory algorithms for outerplanar graphs. doi:10.1007/3-540-46632-0_31
- Date Created
- 1999-01-01
Relations
- In Collection:
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
outerplanar_isaac99.pdf | 2022-08-26 | Public | Download |