License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.7
URN: urn:nbn:de:0030-drops-39175
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3917/
Go to the corresponding LIPIcs Volume Portal

Marx, Dániel

Algorithmic Graph Structure Theory (Tutorial)

pdf-format:
5.pdf (0.3 MB)

Abstract

The Graph Minors project of Robertson and Seymour uncovered a very deep structural theory of graphs. This theory had several important consequences, among others, the proof of Wagner's Conjecture. While the whole theory, presented in a series of 23 very dense papers, is notoriously difficult to understand, it has to be emphasized that these papers introduced several elementary concepts and tools that had strong impact on algorithms, complexity, and combinatorics. Moreover, even some of the very deep results can be stated in a compact and useful way, and it is possible to build upon these results without a complete understanding of the underlying machinery.

In the first part of the lecture, I will introduce the concept of treewidth, which can be thought of as an elementary entry point to graph minors theory. I will overview its graph-theoretic and algorithmic properties that make it especially important in the design of parameterized algorithms and approximation schemes on planar graphs. Furthermore, I will briefly explain some of the connections of treewidth to complexity and automata theory.

In the next part of the lecture, we will turn our attention to the more advanced topic of graphs excluding a fixed minor: the structure of such graphs, finding minors, and the well-quasi-ordering of the minor relation. The primary goal here is to provide clear and useful statements of these results and to show how they generalize the concepts of treewidth and planar graphs. Finally, I will briefly overview some more recent results involving different kinds of excluded structures, such as graphs excluding odd minors and topological minors.

BibTeX - Entry

@InProceedings{marx:LIPIcs:2013:3917,
  author =	{D{\'a}niel Marx},
  title =	{{Algorithmic Graph Structure Theory (Tutorial)}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{7--7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3917},
  URN =		{urn:nbn:de:0030-drops-39175},
  doi =		{10.4230/LIPIcs.STACS.2013.7},
  annote =	{Keywords: Graph theory, graph minors, structure theorems}
}

Keywords: Graph theory, graph minors, structure theorems
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI