Low Polynomial Exclusion of Planar Graph Patterns

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 ($c_{h}=O(h^2\cdot \log^{2} h)$), any graph of pathwidth at most 2 ($c_{h}=O(h^{2})$), and the yurt graph ($c_{h}=O(h^{4})$).
Type de document :
Pré-publication, Document de travail
2013
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904535
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 16:14:57
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

• HAL Id : lirmm-00904535, version 1
• ARXIV : 1305.7112

Citation

Jean-Florent Raymond, Dimitrios M. Thilikos. Low Polynomial Exclusion of Planar Graph Patterns. 2013. 〈lirmm-00904535〉

Métriques

Consultations de la notice