I/O-efficient algorithms on near-planar graphs

H.J. Haverkort, L. Toma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationLATIN 2006: Theoretical Informatics (Proceedings 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006)
EditorsJ.R. Correa, A. Hevia, M. Kiwi
Place of PublicationBerlin
PublisherSpringer
Pages580-591
ISBN (Print)3-540-32755-X
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume3887
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'I/O-efficient algorithms on near-planar graphs'. Together they form a unique fingerprint.

Cite this