Geodesic
I/O-Efficient Algorithms on Near-Planar Graphs
Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 4, pp. 503-532.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2011_15_4_a1,
     author = {Herman Haverkort and Laura Toma},
     title = {I/O-Efficient {Algorithms} on {Near-Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {503--532},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2011},
     doi = {10.7155/jgaa.00236},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00236/}
}
TY  - JOUR
AU  - Herman Haverkort
AU  - Laura Toma
TI  - I/O-Efficient Algorithms on Near-Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 503
EP  - 532
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00236/
DO  - 10.7155/jgaa.00236
LA  - en
ID  - JGAA_2011_15_4_a1
ER  - 
%0 Journal Article
%A Herman Haverkort
%A Laura Toma
%T I/O-Efficient Algorithms on Near-Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2011
%P 503-532
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00236/
%R 10.7155/jgaa.00236
%G en
%F JGAA_2011_15_4_a1
Herman Haverkort; Laura Toma. I/O-Efficient Algorithms on Near-Planar Graphs. Journal of Graph Algorithms and Applications, Tome 15 (2011) no. 4, pp. 503-532. doi : 10.7155/jgaa.00236. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00236/

Cité par Sources :