## 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.
The last meeting is in our seminar room and not mandatory.