Skip Navigation



The Computer Journal Advance Access published online on November 23, 2007
The Computer Journal, doi:10.1093/comjnl/bxm033
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
51/3/292    most recent
bxm033v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Demaine, E. D.
Right arrow Articles by Hajiaghayi, M. T.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2007. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

The Bidimensionality Theory and Its Algorithmic Applications1

Erik D. Demaine1,* and Mohammad Taghi Hajiaghayi1

1 MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA

* Corresponding author: edemaine{at}mit.edu

Received 26 February 2006; revised 10 August 2006

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.

Key Words: graph algorithms • graph minors • bidimensionality

1 A preliminary version of this paper appeared for Proceedings of the 12th International Symposium on Graph Drawing, LNCS 3383, 2004, pages 517–533.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.