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.

Deadlines

TBA