This thesis deals with structural issues in graph theory that arise from algorithmic motivations. Indeed, NP-complete graph problems are typically easier when the class of graphs is restricted.
On trees, which are related graphs without cycles, dynamic programming often gives a linear algorithm. Not all graphs are trees, but it is possible to quantify the extent to which a graph is more complex than a tree. A standard tool for this is treewidth, which is deeply related to the theory of minors, and another strategy is to obtain a tree structure by deleting as few vertices as possible.
The first part of the thesis deals with the idea of universal graphs for the miner relation. A graph is minor-universal for a family of graphs if it contains every graph in the family as a minor. This is because it is easier to manipulate a single graph than an entire family in order to deduce properties. What's more, a famous result by Robertson, Seymour and Thomas links this notion to tree width, focusing in particular on the universal minor of planar graphs. The aim is to extend their result to a larger family.
The second part focuses on the search for a large forest (union of several trees) induced in a graph. Erdős-Pósa's theorem states that if a graph has few disjoint cycles, then it admits a set of vertices of constant size whose elimination produces a forest. We obtain a similar property for a more general family, the counterpart of this generalisation being that the size of this set is then logarithmic in the size of the graph, and this bound can be reached.