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

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
29.06. Baker's approximation scheme for planar graphs Philipp Whittington
29.06. An approximation scheme for planar graph TSP Ahmet Altinbüken
06.07. Treewidth and its characterizations Luca Oeljeklaus
13.07. Treewidth and combinatorial optimization Matthias Mertens
20.07. The Graph Minor Theorem David Kellermann