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.
