Algorithms on Sparse Graphs

Seminar in Theoretical Computer Science, Summer 2018


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 tree-decomposition.
  • The Robertson-Seymour Decomposition Theorem for H-minor-free graphs
  • The Grid Theorem for H-minor-free graphs


Participants should have an interest in algorithms, discrete mathematics, graph theory and (in general) theoretical computer science.



The meeting is always Fridays in room 5055 at 12:15.

Date Topic Student Material
27.04. Efficient Planarity Testing Kevin Behrens Slides, Ausarbeitung
04.05. Embedding Planar Graphs Using PQ-Trees Niklas KotowskiSlides, Ausarbeitung
18.05. The planar separator theorem Aleksandar TimanovSlides
15.06. Flows in planar graphs Robin Münstermann Slides
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
13.07. An approximation scheme for planar graph TSP Ahmet Altinbüken Slides
13.07. Treewidth and combinatorial optimization Luca Oeljeklaus
20.07. The Graph Minor Theorem David Kellermann