Back to search

National and Kapodistrian University of Athens

Obstructions and algorithms for graph layouts problems

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/41215

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Zoros, Dimitris; Ζώρος, Δημήτριος. Obstructions and algorithms for graph layouts problems. National and Kapodistrian University of Athens, 2017. http://hdl.handle.net/10442/hedi/41215