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] [Accessibility]

Lecture 1 Video [next]

[+] Introduction: Graphs considered: planar, bounded-genus, apex-minor-free, H-minor-free. Problems considered and survey of results.

This lecture is an introduction to the whole class, in particular an overview of the different types of graphs that we'll be talking about (the mysterious “Beyond” in the title). We also survey many different problems where we can do a lot better on planar graphs than we can on general graphs, to give you a flavor of what we will learn in the class.

Download Video: 360p, 720p

Lecture notes, page 1/9 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.