Contracting planar graphs to contractions of triangulations

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

Research output: Contribution to journalArticlepeer-review

Abstract

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H C, there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class C is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph H C if and only if there exists a constant cH such that if the treewidth of a graph is at least cH, it contains H as a contraction. We also provide a characterization of C in terms of minimal forbidden contractions.

Original languageEnglish (US)
Pages (from-to)299-306
Number of pages8
JournalJournal of Discrete Algorithms
Volume9
Issue number3
DOIs
StatePublished - Sep 2011

Keywords

  • Contraction
  • Dual graph
  • Fixed parameter tractable
  • Planar graph
  • Topological minor

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Contracting planar graphs to contractions of triangulations'. Together they form a unique fingerprint.

Cite this