Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00082
I/OOptimal Algorithms for Outerplanar Graphs
Vol. 8, no. 1, pp. 4787, 2004. Regular paper.
Abstract We present linearI/O algorithms for fundamental graph problems on
embedded outerplanar graphs. We show that
breadthfirst search, depthfirst search, singlesource shortest
paths, triangulation, and computing an ϵseparator of
size O(1/ϵ) take O(scan(N)) I/Os on embedded
outerplanar graphs. We also show that it takes O(sort(N)) I/Os
to test whether a given graph is outerplanar and to compute an
outerplanar embedding of an outerplanar graph, thereby providing
O(sort(N))I/O algorithms for the above problems if no
embedding of the graph is given. As all these problems have
lineartime algorithms in internal memory, a simple simulation
technique can be used to improve the I/Ocomplexity of our
algorithms from O(sort(N)) to O(perm(N)). We prove matching
lower bounds for embedding, breadthfirst search, depthfirst
search, and singlesource shortest paths if no embedding is given.
Our algorithms for the above problems use
a simple linearI/O timeforward processing algorithm for
rooted trees whose vertices are stored in preorder.

Journal Supporters
