Contractions of planar graphs in polynomial time

Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

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


We prove that for every graph H, there exists a polynomial-time algorithm deciding if a planar graph can be contracted to H. We introduce contractions and topological minors of embedded (plane) graphs and show that a plane graph H is an embedded contraction of a plane graph G, if and only if, the dual of H is an embedded topological minor of the dual of G. We show how to reduce finding embedded topological minors in plane graphs to solving an instance of the disjoint paths problem. Finally, we extend the result to graphs embeddable in an arbitrary surface.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Number of pages12
EditionPART 1
StatePublished - 2010
Event18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom
Duration: Sep 6 2010Sep 8 2010

Publication series

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


Conference18th Annual European Symposium on Algorithms, ESA 2010
Country/TerritoryUnited Kingdom


  • contraction
  • dual graph
  • planar graph
  • topological minor

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Contractions of planar graphs in polynomial time'. Together they form a unique fingerprint.

Cite this