Low Polynomial Exclusion of Planar Graph Patterns

Jean-Florent Raymond 1 Dimitrios M. Thilikos 1, 2
1 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 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⋅log2h) ), any graph of pathwidth at most 2 (ch=O(h2) ), and the yurt graph (ch=O(h4) ).
Keywords : graph minors treewidth
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2015, 〈10.1002/jgt.22009〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263767
Contributeur : Jean-Florent Raymond <>
Soumis le : jeudi 28 janvier 2016 - 11:15:15
Dernière modification le : vendredi 5 octobre 2018 - 21:14:01
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 18:10:14

Fichier

lowpolex.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Florent Raymond, Dimitrios M. Thilikos. Low Polynomial Exclusion of Planar Graph Patterns. Journal of Graph Theory, Wiley, 2015, 〈10.1002/jgt.22009〉. 〈lirmm-01263767〉

Partager

Métriques

Consultations de la notice

130

Téléchargements de fichiers

181