Algorithms on Sparse Graphs
ContentIn 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
PrerequisitesParticipants should have an interest in algorithms, discrete mathematics, graph theory and (in general) theoretical computer science.
TalksThese are the talks that we've had thus far.
- Mirko Kugelmeier. Efficient Planarity Testing. (29 Oct)
- Phillip Kessels. Embedding Planar Graphs Using PQ-Trees. (12 Nov)
- Jan Dreier. The planar separator theorem. (12 Nov)
- Sascha Kurowski. Shortest paths in undirected planar graphs with nonnegative weights. (19 Nov)
- Sebastian Addicks. Shortest paths in directed planar graphs with negative weights. (19 Nov)
- Thomas Prinz. Shortest paths in planar graphs with real weights. (26 Nov)
- Kiril Mitev. Max-Flow Min Cut in undirected planar graphs. (26 Nov)
- Oliver Kotulski. Maximum s-t . flows on directed planar graphs. (3 Dec)
- Marius Knabben. Approximation algorithms for NP-complete problems on planar graphs. (10 Dec)
- Thomas Grzanna. An approximation scheme for planar graph TSP. (17 Dec)