@inproceedings{9c752e90af584e4d919817795841c572,

title = "I/O-efficient algorithms on near-planar graphs",

abstract = "Obtaining I/O-efficient algorithms for basic graph problems on sparse directed graphs is a long-standing open problem. While the best known upper bounds for most basic problems on such graphs with V vertices still require O(V ) I/Os, 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 give a characterization of near-planarity which covers a wide range of near-planar graphs, and obtain the first I/O-efficient algorithms for directed graphs that are near-planar.",

author = "H.J. Haverkort and L. Toma",

year = "2006",

doi = "10.1007/11682462_54",

language = "English",

isbn = "3-540-32755-X",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "580--591",

editor = "J.R. Correa and A. Hevia and M. Kiwi",

booktitle = "LATIN 2006: Theoretical Informatics (Proceedings 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006)",

address = "Germany",

}