Cette thèse traite des questions structurelles de la théorie des graphes qui découlent de motivations algorithmiques. En effet, les problèmes de graphes NP-complets sont typiquement plus faciles dès lors qu'on restreint la classe de graphes.
Sur les arbres, qui sont des graphes connexes sans cycles, la programmation dynamique donne souvent un algorithme linéaire. Tous les graphes ne sont pas des arbres, mais il est possible de quantifier à quel point un graphe est plus complexe qu'un arbre. Un outil standard pour cela est la largeur arborescente, qui est profondément liée à la théorie des mineurs, et une autre stratégie consiste à obtenir une structure arborescente en supprimant le moins de sommets possible.
La première partie de la thèse porte sur l'idée de graphes universels pour la relation de mineur. Un graphe est mineur-universel pour une famille de graphes s'il contient comme mineur chaque graphe de la famille. Il est en effet plus aisé de manipuler un unique graphe plutôt qu’une famille entière pour en déduire des propriétés. De plus, un résultat célèbre de Robertson, Seymour et Thomas lie cette notion à la largeur arborescente, en s’intéressant en particulier au mineur-universel des graphes planaires. Le but est d’étendre leur résultat à une famille plus vaste.
La deuxième partie se concentre sur la recherche d'une grande forêt (union de plusieurs arbres) induite dans un graphe. Le théorème d’Erdős-Pósa stipule que si un graphe a peu de cycles disjoints, alors il admet un ensemble de sommets de taille constante dont l'élimination produit une forêt. Nous obtenons une propriété similaire pour une famille plus générale, la contrepartie de cette généralisation étant que la taille de cet ensemble est alors logarithmique en la taille du graphe, et cette borne peut être atteinte.