Low Polynomial Exclusion of Planar Graph Patterns

Jean Florent Raymond; Dimitrios M. Thilikos

doi:10.1002/jgt.22009

Low Polynomial Exclusion of Planar Graph Patterns

Jean Florent Raymond, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

The celebrated grid exclusion theorem states that for every h-vertex planar graph H, there is a constant C_h such that if a graph G does not contain H as a minor then G has treewidth at most C_h. 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 (c_h = O(h)), the double wheel (ch = O(h² · log² h)), any graph of pathwidth at most 2 (c_h = O(h²)), and the yurt graph (c_h = O(h⁴)).

Original language	English (US)
Pages (from-to)	26-44
Number of pages	19
Journal	Journal of Graph Theory
Volume	84
Issue number	1
DOIs	https://doi.org/10.1002/jgt.22009
State	Published - Jan 1 2017

Keywords

graph minors
treewidth

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.22009

Cite this

@article{13c2ad04aca04cd6bdd004c1584ace95,

title = "Low Polynomial Exclusion of Planar Graph Patterns",

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)).",

keywords = "graph minors, treewidth",

author = "Raymond, {Jean Florent} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2015 Wiley Periodicals, Inc.",

year = "2017",

month = jan,

day = "1",

doi = "10.1002/jgt.22009",

language = "English (US)",

volume = "84",

pages = "26--44",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Low Polynomial Exclusion of Planar Graph Patterns

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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)).

AB - 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)).

KW - graph minors

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=84995578555&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84995578555&partnerID=8YFLogxK

U2 - 10.1002/jgt.22009

DO - 10.1002/jgt.22009

M3 - Article

AN - SCOPUS:84995578555

SN - 0364-9024

VL - 84

SP - 26

EP - 44

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Low Polynomial Exclusion of Planar Graph Patterns

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this