Algorithms on Sparse Graphs

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.

Deadlines

Talks

These are the talks that we've had thus far.
  1. Mirko Kugelmeier. Efficient Planarity Testing. (29 Oct)
  2. Phillip Kessels. Embedding Planar Graphs Using PQ-Trees. (12 Nov)
  3. Jan Dreier. The planar separator theorem. (12 Nov)
  4. Sascha Kurowski. Shortest paths in undirected planar graphs with nonnegative weights. (19 Nov)
  5. Sebastian Addicks. Shortest paths in directed planar graphs with negative weights. (19 Nov)
  6. Thomas Prinz. Shortest paths in planar graphs with real weights. (26 Nov)
  7. Kiril Mitev. Max-Flow Min Cut in undirected planar graphs. (26 Nov)
  8. Oliver Kotulski. Maximum s-t . flows on directed planar graphs. (3 Dec)
  9. Marius Knabben. Approximation algorithms for NP-complete problems on planar graphs. (10 Dec)
  10. Thomas Grzanna. An approximation scheme for planar graph TSP. (17 Dec)