Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “The Bidimensionality Theory and Its Algorithmic Applications”, The Computer Journal, volume 51, number 3, 2008, pages 292–302.

Abstract:

This paper surveys the theory of bidimensionality. This theory characterizes a broad range of graph problems (“bidimensional”) that admit efficient approximate or fixed-parameter solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs, and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the Graph Minor Theory of Robertson and Seymour, by extending the mathematical results and building new algorithmic tools. Here we summarize the known combinatorial and algorithmic results of bidimensionality theory, with the high-level ideas involved in their proof; we describe the previous work on which the theory is based and/or extends; and we mention several remaining open problems.

Comments:

This paper is also available from Oxford Journals.

Copyright:

Copyright held by the authors.

Availability:

The paper is available in PostScript (514k), gzipped PostScript (214k), and PDF (328k).

See information on file formats.

[Google Scholar search]

Related papers:

BidimensionalSurvey_GD2004 (Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth)