Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00236
I/OEfficient Algorithms on NearPlanar Graphs
Herman Haverkort and
Laura Toma
Vol. 15, no. 4, pp. 503532, 2011. Regular paper.
Abstract Obtaining I/Oefficient algorithms for basic graph problems on sparse
directed graphs has been a longstanding 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/Oefficiently. 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/Oefficient 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 E_{C}. Our main result is a
singlesourceshortestpaths algorithm that runs in O(E_{C} + sort(V +E_{C})) I/Os. When E_{C} 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 singlesource shortest paths in
O(sort(V + T)) I/Os. We obtain similar bounds for computing
(strongly) connected components, breadthfirst and depthfirst
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

Journal Supporters
