Summary:
Many combinatorial computational problems are considered in their general
form intractable, in the sense that even for modest size problems, providing
an exact optimal solution is practically infeasible, as it typically involves
the
use of algorithms whose running time is exponential in the size of the problem.
Often these problems can be modeled by graphs. Then, additional structural
properties of a graph, such as surface embeddability, can provide a handle for
the design of more ecient algorithms. The theory of Bidimensionality, dened
in the context of Parameterized Complexity, builds on the celebrated results of
Graph Minor theory and establishes
a meta algorithmic framework for addressing problems in a broad range of graph
classes, namely all generalizations of graphs embeddable on some surface. In
this doctoral thesis we explore topics of combinatorial nature related to the
implementation of the theory of Bidimensionality and to the possibilities of
the extension of its applicability range.
Keywords:
Bidimensionality, Algoritms, Graph Theory, Matroid Theory, Minors