I/O-Efficient Algorithms on Near-Planar Graphs
Herman Haverkort and Laura Toma
Vol. 15, no. 4, pp. 503-532, 2011. Regular paper.
Abstract Obtaining I/O-efficient algorithms for basic graph problems on sparse directed graphs has been a long-standing open problem. The best known algorithms for most basic problems on such graphs still require Ω(V) I/Os in the worst case, where V is the number of vertices in the graph. Nevertheless optimal O(sort(V)) I/O algorithms are known for special classes of sparse graphs, like planar graphs and grid graphs. It is hard to accept that a problem becomes difficult as soon as the graph contains a few deviations from planarity.
In this paper we extend the class of graphs on which basic graph problems can be solved I/O-efficiently. We discuss several ways to transform graphs that are almost planar into planar graphs (given a suitable drawing), and based on those transformations we obtain the first I/O-efficient algorithms for directed graphs that are almost planar.
Let G be a directed graph that is given as a planar subgraph (V,E) and a set of additional edges EC. Our main result is a single-source-shortest-paths algorithm that runs in O(EC + sort(V +EC)) I/Os. When EC is small our algorithm is a significant improvement over the best previously known algorithms, which required Ω(V) I/Os. Alternatively, when G is given with a drawing with T crossings, we can compute single-source shortest paths in O(sort(V + T)) I/Os. We obtain similar bounds for computing (strongly) connected components, breadth-first and depth-first traversals and topological ordering.
Submitted: May 2007.
Reviewed: April 2008.
Revised: June 2008.
Reviewed: July 2009.
Revised: December 2010.
Accepted: July 2011.
Final: August 2011.
Published: September 2011.
Communicated by Larse Arge
article (PDF)