Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 5 Video [previous] [next]

[+] Vector spaces and Separators

We use vector spaces for graphs to prove the duality of simple cycles and simple cuts, and the existence of interdigitationg trees. In the last part of the class we start discussing separators. Our discussion begins with showing the existence of a balanced edge separator for trees and of fundamental cycle separators for planar graphs.

Download Video: 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 me.