Contraction bidimensionality: The accurate picture

Fedor V. Fomin, Petr Golovach, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Number of pages12
StatePublished - 2009
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: Sep 7 2009Sep 9 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5757 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th Annual European Symposium on Algorithms, ESA 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Contraction bidimensionality: The accurate picture'. Together they form a unique fingerprint.

Cite this