Robertson et Seymour ont introduit les décompositions
arborescentes qui constituent un outil puissant pour l'étude de
graphes, tant d'un point de vue théorique qu'algorithmique En
effet, de nombreux problèmes NP-complets deviennent polynômiaux
quand on se restreint aux classes de graphes admettant une
décomposition de largeur bornée. Cependant, si Robertson et
Seymour ont montré que de telles classes se
caractérisent par des mineurs planaires interdits, leurs bornes
sont doublement exponentielles en la taille de ces mineurs, ce qui
contribue à rendre les algorithmes inutilisables.
En considérant trois manières différentes
d'appréhender les décompositions arborescentes, nous
donnerons des bornes polynômiales pour la largeur arborescente des
graphes sans longs circuits ou sans prismes.