Algorithms on Sparse Graphs
Seminar in Theoretical Computer Science, Summer 2018
Content
In this seminar, we wish to study algorithmic aspects of sparse graphs.
A useful working definition of a sparse graph is one in which the number
of edges is a linear function of the number of vertices. Examples include
planar graphs, graphs of bounded treewidth, graphs that exclude fixed graph
as a minor or topological minor.
Some of the topics that we wish to study are:
 Testing whether a given graph is planar.
 Planar Separator Theorems.
 Flows and shortest path algorithms in planar graphs.
 Properties of graphs of bounded treewidth; comptuting an approximate treedecomposition.
 The RobertsonSeymour Decomposition Theorem for Hminorfree graphs
 The Grid Theorem for Hminorfree graphs
Prerequisites
Participants should have an interest in algorithms,
discrete mathematics, graph theory and (in general)
theoretical computer science.
Material
Schedule
The meeting is always Fridays in room 5055 at 12:15.
The last meeting is in our seminar room and not mandatory.
Date

Topic

Student

Material

27.04.  Efficient Planarity Testing  Kevin Behrens  Slides, Ausarbeitung 
04.05.  Embedding Planar Graphs Using PQTrees  Niklas Kotowski  Slides, Ausarbeitung 
18.05.  The planar separator theorem  Aleksandar Timanov  Slides 
15.06.  Flows in planar graphs  Robin Münstermann  Slides, Ausarbeitung 
22.06.  Embedding planar graphs on a grid  Pascal Hein  Slides, Ausarbeitung 
29.06.  Baker's approximation scheme for planar graphs  Philipp Whittington  Slides 
06.07.  Treewidth and its characterizations  Matthias Mertens  Slides 
13.07.  An approximation scheme for planar graph TSP  Ahmet Altinbüken  Slides 
13.07.  Treewidth and combinatorial optimization  Luca Oeljeklaus  Slides 
03.08.  The Graph Minor Theorem  David Kellermann  