Obstructions and algorithms for graph layouts problems

Abstract

Modern Graph Theory is heavily influenced by the seminal work of N. Robertson and P. Seymour, known as Graph Minors. Through this work, a wealth of structural, combinatorial, as well as algorithmic, results has been introduced, in a series of papers having as ultimate goal to give an affirmative answer to Wagner’s Conjecture. In this doctoral thesis we focus on the study of Obstruction Sets, one of the most important combinatorial concepts of this theory. In particular, we study the combinatorics and the algorithmic and computability aspects of graph obstructions and their relation to graph parameters emerging from Graph Layouts, Vertex Deletion Problems, and Graph Searching Problems. We consider several partial ordering relations on graphs such as minors, immersions, and contractions. Our study includes results on the existence and the computability of obstruction sets, combinatorial bounds on their size, and their interplay with parameterized complexity and kernelization.

Η σύγχρονη Θεωρία Γραφημάτων έχει επηρεαστεί σε μεγάλο βαθμό από την δουλειά των N. Robertson και P. Seymour. έσα από αυτήν, πληθώρα από δομικά, συνδυαστικά, καθώς και αλγοριθμικά αποτελέσματα εισήχθηκαν, σε μία σειρά από εργασίες που είχε απώτερο στόχο την απόδειξη της εικασίας του Wagner. Σε αυτή την διδακτορική διατριβή επικεντρωνόμαστε στην μελέτη των Συνόλων Παρεμπόδισης, μία από τις σημαντικότερες συνδυαστικές έννοιες αυτής της θεωρίας. Πιο συγκεκριμένα, μελετάμε την συνδυαστική και αλγοριθμική πτυχή, καθώς και την υπολογισιμότητα, των γραφημάτων παρεμπόδισης, σε σχέση με παραμέτρους γραφημάτων που πηγάζουν από Διατάξεις σε Γραφήματα, Προβλήματα Διαγραφής ορυφών και Προβλήματα Ανίχνευσης Γραφημάτων. Η μελέτη αυτή είναι βασισμένη σε σχέσεις μερικής διάταξης γραφημάτων, όπως τα ελάσσονα, οι εμβυθίσεις και οι συνθλίψεις. Η μελέτη μας περιλαμβάνει αποτελέσματα σχετικά με την ύπαρξη και υπολογισιμότητα των συνόλων παρεμπόδισης, συνδυαστικά φράγματα στο μέγεθος τους, καθώς και την αλληλεπίδρασή τους με την Παραμετρική Πολυπλοκότητα και την Πυρηνοποίηση.