Algorithms for Planar Graphs (Fall 2013)

Shay Mozes

Lecture 12 Video [previous] [next]

[+] Maximum st-flow in directed planar graphs

We describe an O(nlog n)-time algorithm for finding a maximum st-flow in directed planar graphs. The algorithm, due to Borradaile and Klein, resembles the MSSP algorithm, with the roles of primal and dual swapped. It maintains a dual shortest path tree as the (value of the) flow is increased, until a cycle is introduced into the dual tree, which corresponds to a saturated st-cut in the primal. Most of the lecture is devoted to analyzing the number of pivots performed by the algorithm. We present the analysis of Erickson, which uses a universal cover of the dual graph to show that each dart is ejected from the dual tree at most once.

Download Video: 360p, 720p

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