Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 6 Video [previous] [next]

[+] Separators

We discuss a linear time algorithm for finding a small vertex separator in planar graphs. We then show an example of using such separators for finding maximum matchings. Finally, we start describing how to find small simple cycle separators in planar graphs. The algorithm builds on that of the vertex separator, but uses BFS levels in the face-vertex incidence graph (radial graph).

Download Video: 720p

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