LARGE DIRECTED GRAPHS - THE NEW FRONTIER?

solution of fundamental problems on undirected graphs, researchers in the area
of I/O-efficient graph algorithms have identified the development of
I/O-efficient algorithms for directed graphs as one of the most important
frontiers of research in this area. We began to do research in this direction
by considering those classes of graphs that allow I/O-optimal solutions to a
number of fundamental problems if the graph is undirected. Even though the fact
that edges are now directed complicates matters, it turns out that for these
graphs, most problems that can be solved I/O-optimally in the undirected case
can also be solved I/O-optimally in the directed case. We conclude that the
development of I/O-efficient algorithms for general directed graphs is the big
challenge.

To illustrate the ideas that lead to I/O-efficient algorithms on special
classes of sparse graphs, we consider two problems on directed planar graphs:
topological sorting of planar DAGs and computing the strongly connected
components of a directed planar graph. Besides being a fundamental problem in
its own right, topological sorting has gained importance in the area of
I/O-efficient graph algorithms because it is a prerequisite for the so-called
time-forward processing technique, which is applied in a large number of
I/O-efficient graph algorithms.