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 18 Video [previous] [next]

[+] Flow in planar graphs I: undirected min cut, circulations and max-flow in st-planar graphs.

We discuss Reif's algorithm for computing the minimum st-cut in an undirected planar graph. We then start treating flows in directed planar graphs by studying circulations and their relation to shortest paths and negative-length cycles in the dual. We use these concepts in a linear-time algorithm for maximum flow in the special case where the source and sink lie on the same face (st-planar graphs).

Download Video: 360p, 720p

Lecture notes, page 1/14 • [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.