Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF]
[+] Planar separators: Lipton-Tarjan and Miller's separators, r-divisions. |
|
Many efficient algorithms for planar graphs make use of «small
separators»:
small cuts that partition the graph into roughly balanced pieces.
Such separators often allow us to apply a divide-and-conquer
paradigm,
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. |
|
Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
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 Erik.