Low Polynomial Exclusion of Planar Graph Patterns

Jean Florent Raymond, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

The celebrated grid exclusion theorem states that for every h-vertex planar graph H, there is a constant Ch such that if a graph G does not contain H as a minor then G has treewidth at most Ch. We are looking for patterns of H where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel (ch = O(h)), the double wheel (ch = O(h2 · log2 h)), any graph of pathwidth at most 2 (ch = O(h2)), and the yurt graph (ch = O(h4)).

Original languageEnglish (US)
Pages (from-to)26-44
Number of pages19
JournalJournal of Graph Theory
Volume84
Issue number1
DOIs
StatePublished - Jan 1 2017

Keywords

  • graph minors
  • treewidth

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Low Polynomial Exclusion of Planar Graph Patterns'. Together they form a unique fingerprint.

Cite this