Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 11 Video [previous] [next]

[+] Branch decomposition and Tamaki's theorem

We define carving and branch decompositions and show how to solve vertex cover using a dynamic program on the branch decomposition. Given a planar graph, we show how to find a carving decomposition whose width is related to the radius of the dual graph. We use this to prove Tamaki's theorem which shows (algorithmically) the existence of a branch decomposition whose width is roughly twice the minimum between the primal and dual radii.

Download Video: 720p

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