[+] Planar separators: Lipton-Tarjan and Miller's separators, r-divisions.
Many efficient algorithms for planar graphs make use of «small
small cuts that partition the graph into roughly balanced pieces.
Such separators often allow us to apply a divide-and-conquer
recursively separating the graph to end up with small pieces with even
smaller boundaries. These and related techniques are used in many
algorithms we'll be presenting throughout the course.
In this lecture, we discuss linear-time algorithms for planar graphs
that find a small (O(√n)) subset of the nodes whose removal partitions
the graph into disjoint subgraphs of size at most 3n/4.
Based on interdigitating trees from Lecture 2, we first devise fundamental-cycle separators. We then show how to reduce the length of these cycles (1) by cutting the graph into pieces with smaller diameter and, if time permits, (2) by merging faces.
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.