Paper by Erik D. Demaine
- Erik D. Demaine and MohammadTaghi Hajiaghayi, “The Bidimensionality Theory and Its Algorithmic Applications”, The Computer Journal, volume 51, number 3, 2008, pages 292–302.
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.
- This paper is also available from Oxford Journals.
- Copyright held by the authors.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 14, 2022 by