Optimizing the Graph Minors Weak Structure Theorem

Archontia C. Giannopoulou 1, 2 Dimitrios M. Thilikos 3, 1
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : One of the major results of [N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65--110], also known as the weak structure theorem, reveals the local structure of graphs excluding some graph as a minor: each such graph $G$ either has small treewidth or contains the subdivision of a planar graph (a wall) that can be arranged in a flat manner inside $G$, given that some small set of vertices is removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized.
Keywords : treewidth graph minors
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2013, 27 (3), pp.1209-1227. 〈http://epubs.siam.org/doi/abs/10.1137/110857027〉. 〈10.1137/110857027〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904527
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 16:07:57
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Archontia C. Giannopoulou, Dimitrios M. Thilikos. Optimizing the Graph Minors Weak Structure Theorem. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2013, 27 (3), pp.1209-1227. 〈http://epubs.siam.org/doi/abs/10.1137/110857027〉. 〈10.1137/110857027〉. 〈lirmm-00904527〉

Partager

Métriques

Consultations de la notice

90