ALCOMFT-TR-01-93

Lars Arge, Ulrich Meyer, Laura Toma and Norbert Zeh
On External-Memory Planar Depth First Search
MPI. Work packages 1, 2 and 4. May 2001.

Abstract: Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open. For example, no space- and I/O-efficient algorithms are known for depth-first search or breadth-first search in sparse graphs. In this paper we present two new results on I/O-efficient depth-first search in an important class of sparse graphs, namely undirected embedded planar graphs. We develop a new efficient depth-first search algorithm and show how planar depth-first search in general can be reduced to planar breadth-first search. As part of the first result we develop the first I/O-efficient algorithm for finding a simple cycle separator of a biconnected planar graph. Together with other recent reducibility results, the second result provides further evidence that external memory breadth-first search is among the hardest problems on planar graphs.

Postscript file: ALCOMFT-TR-01-93.ps.gz (117 kb).