## 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.- 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*(3 Dec)*s-t*. flows on directed planar graphs. - Marius Knabben.
*Approximation algorithms for NP-complete problems on planar graphs.*(10 Dec) - Thomas Grzanna.
*An approximation scheme for planar graph TSP.*(17 Dec)