Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

On External-Memory Planar Depth First Search


Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Zeh,  Norbert
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Arge, L., Meyer, U., Toma, L., & Zeh, N. (2001). On External-Memory Planar Depth First Search. In F. Dehne, J.-R. Sack, & R. Tamassia (Eds.), Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS-01) (pp. 471-482). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-31A7-5
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.