Décompositions en branches et graphes planaires

Dans leur longue série d’articles sur les mineurs de graphes, Robertson et Seymour ont défini une nouvelle classe de décompositions des graphes – les décompositions en branches – pour obtenir une obstruction aux décompositions arborescente. Cette obstruction a permis à Seymour et Thomas, en calculant exactement la largeur de branches des graphes planaires, de donner la meilleure approximation de la largeur arborescente des graphes planaires.

Je montrerai comment unifier ces deux types de décompositions à l’aide d’un nouvel objet combinatoire : les matriochkas. Ces matriochkas permettent de mieux comprendre les liens mais aussi les différences entre les décompositions arborescentes et les décompositions en branches. En les utilisant, il est aussi possible de transférer des résultats d’une des décompositions à l’autre. Je présenterai une nouvelle démonstration du fait que la largeur arborescente d’un graphe planaire et celle de son dual diffèrent au plus d’un, démonstration que j’ai obtenue de cette façon.