Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth”, in Proceedings of the 12th International Symposium on Graph Drawing (GD 2004), Lecture Notes in Computer Science, volume 3383, Harlem, New York, September 29–October 2, 2004, pages 517–533.

Abstract:

This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory is based, and the remaining open problems.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 17 pages.

Availability:

The paper is available in PostScript (363k), gzipped PostScript (164k), and PDF (241k).

See information on file formats.

[Google Scholar search]

Related papers:

BidimensionalSurvey_CJ (The Bidimensionality Theory and Its Algorithmic Applications)