National and Kapodistrian University of Athens
Obstructions and algorithms for graph layouts problems
Abstract
dc:descriptionModern 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.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Zoros, Dimitris
- Ζώρος, Δημήτριος
Subjects
dc:subject × 24- Παρεμποδίσεις
- Διατάξεις γραφημάτων
- Θεωρία γραφημάτων
- Παραμετρική πολυπλοκότητα
- Ανίχνευση σε γραφήματα
- Ελάσσονα γραφήματος
- Εμβυθίσεις γραφήματος
- Συνθλίψεις γραφήματος
- Πλάτος τομών
- Πυρηνοποίηση
- Obstructions
- Graph layouts
- Graph theory
- Graph searching
- Graph minors
- Graph immersions
- Graph contractions
- Cutwidth
- Kernelization
- Parameterized complexity
- Φυσικές Επιστήμες
- Μαθηματικά
- Natural Sciences
- Mathematics
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/41215