6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari


[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book]

Overview

Solve your favorite problems faster for graphs that matter!

Graphs in the real world tend to have a lot of special structure. In particular, graphs arising on this planet are often planar (or nearly so), meaning that they can be drawn in the plane or a sphere without any (or with few) edge crossings. This class is about efficient algorithms that exploit the structure of planar graphs and related graph classes, specifically graphs embeddable on a surface of low genus and graphs excluding a minor. We will focus on recent results in this exciting area (which all of the instructors actively do research in).

We will organize an optional problem-solving session, during which we can jointly try to solve open problems. In the past, these sessions have led to important new results and published papers, as well as class projects.

Class projects more generally can take the form of formulations of clean, new open problems; implementations of existing algorithms; or well-written descriptions of one or more papers in the area. Projects can be purely mathematical and/or theoretical computer science (algorithmic/complexity theoretic), or purely practical.

Topics

Algorithms for Fundamental Problems: shortest paths, multiple source shortest paths, distance oracles, min-cut, max-flow, TSP, subset TSP, and Steiner tree

Graph Classes: planar graphs, bounded-genus graphs, apex-minor-free graphs, H-minor-free graphs

Techniques: duality, cut-cycle duality, combinatorial embeddings, spanning trees (primal, dual), fundamental cycles, planar separator theorems (Lipton-Tarjan, Miller), recursive r-divisions, treewidth and branchwidth, dynamic programming, Baker's technique, fixed-parameter tractability, grids, bidimensionality, contraction decomposition, Borradaile-Klein

Specifics

Lecture Time: Mondays and Wednesdays at 11:00am–12:30pm
Lecture Room: 2-139
First Lecture: Wednesday, September 7, 2011
Problem Session Time: Wednesdays, 4-6pm
Problem Session Room: 32-G531
Instructors: Prof. Erik Demaine, 32-G680
Shay Mozes
Dr. Christian Sommer, 32-G578
Dr. Siamak Tazari, 32-G578

You can reach all the instructors of 6.889 by sending an email to 6889-staff K5 csail.mit.edu (replace the clique by an @).

Units: 3-0-9
Prerequisites: 6.046 or equivalent background in discrete mathematics and algorithms
Alternatively, permission from the instructor.
Credit: H-level and EC-level credit; no ED credit
Requirements: Written project and project presentation. Small number of problem sets.
Textbook: "Optimization Algorithms for Planar Graphs" by Philip N. Klein (draft).

Participating

We welcome both undergraduate and graduate students from all universities, although officially this is a graduate class.

If you are interested in attending the class, for credit or as a listener, please join the 6889-students mailing list.

Previous Offerings

This is the first time a class like this is offered at MIT. A related class has been offered before as CS 250 / CSCI 2950-R : Planar Graph Algorithms at Brown University by Philip N. Klein.