Summary:
In the Graph Minors project, N. Robertson and P. Seymour, proved a series of
structural and
algorithmic results. Some of them, such as the Strong and the Weak Structure
Theorem, the Excluded
Grid Theorem and the algorithm for Minor Containment, constitute a rich source
of many more structural as well as algorithmic results.
Furthermore, the development of Graph Minor Theory coincided with and
influenced the development
of a new branch of Complexity, namely the Parameterized Complexity Theory,
introduced by R. Downey and M. Fellows. In this doctoral thesis we deal with a
series of issues in Graph Minor Theory and Parameterized Complexity as well as
the dependence of these two areas.
Keywords:
Graph Minor Theory , Graph Searching , Excluded Grid Theorem, Bidimenstionality Theory, Treewidth