Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές

Abstract

Many combinatorial computational problems are considered in their generalform intractable, in the sense that even for modest size problems, providingan exact optimal solution is practically infeasible, as it typically involves theuse of algorithms whose running time is exponential in the size of the problem.Often these problems can be modeled by graphs. Then, additional structuralproperties of a graph, such as surface embeddability, can provide a handle forthe design of more ecient algorithms.The theory of Bidimensionality, dened in the context of ParameterizedComplexity, builds on the celebrated results of Graph Minor theory and establishesa meta algorithmic framework for addressing problems in a broadrange of graph classes, namely all generalizations of graphs embeddable onsome surface.In this doctoral thesis we explore topics of combinatorial nature related tothe implementation of the theory of Bidimensionality and to the possibilitiesof the extension of its applicability range.