Fast minor testing in planar graphs

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C u and C v . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time O(2 O(h) · n+n 2·log n) a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.

Original languageEnglish (US)
Pages (from-to)69-84
Number of pages16
JournalAlgorithmica
Volume64
Issue number1
DOIs
StatePublished - Sep 2012

Keywords

  • Branchwidth
  • Dynamic programming
  • Graph minors
  • Parameterized complexity
  • Planar graphs

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Fast minor testing in planar graphs'. Together they form a unique fingerprint.

Cite this