We present linear-I/O algorithms for fundamental graph problems on embedded outerplanar graphs. We show that breadth-first search, depth-first search, single-source shortest paths, triangulation, and computing an eseparator of sizeO (l / e) take O(scan(iV)) I/Os on embedded outerplanar graphs. We also show that it takes O(sort(AT)) I/Os to test whether a given graph is outerplanar and to compute an outerplanar embedding of an outerplanar graph, thereby providing 0(sort(Af))-I/O algorithms for the above problems if no embedding of the graph is given. As all these problems have Mnear-time algorithms in internal memory, a simple simulation technique can be used to improve the I/O-complexity of our algorithms from O(soit(N)) to O(perm(N)). We prove matching lower bounds for embedding, breadth-first search, depth-first search, and singlesource shortest paths if no embedding is given. Our algorithms for the above problems use a simple linear-I/O time-forward processing algorithm for rooted trees whose vertices are stored in preorder.

Additional Metadata
Persistent URL dx.doi.org/10.1142/9789812773289_0005
Citation
Maheshwari, A, & Zeh, N. (Norbert). (2006). I/O-optimal algorithms for outerplanar graphs. doi:10.1142/9789812773289_0005