Algorithms for Planar Graphs (Fall 2013)

Shay Mozes

Lecture 9 Video [previous] [next]

[+] Branchwidth and Baker's approximation technique

We redefine branchwidth and review 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. We discuss Baker's approximation technique which breaks a planar graph into subgraphs induced by vertices at a constant number of consecutive BFS levels. By Tamaki's theorem each subgraph has constant branchwidth, so can be solved optimally using DP. The optimal solutions from all subgraph are combined to give a near-optimal solution in the entire graph.

Download Video: 360p, 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.