Tag Archives: lecture notes

Lecture notes for Baker's technique for PTASes in planar graphs

In teaching so far, I have relied almost exclusively on textbooks and other people’s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students.  Yes, I would recommend this to anyone who has not been teaching for too long.  Preparing lecture notes that are hand-out-to-your-students worthy is time consuming!  Especially when you are a perfectionist.

I’m teaching a grad course on approximation algorithms right now, using Vijay Vazirani’s book.  (Yes.  Those of us on the quarter system are still teaching.)  I wanted to teach Baker’s technique for giving PTASes on planar graphs as it is beautiful and close to my heart.  By heart, I mean brain.  I only wanted to spend a lecture or two on it and my students don’t know what treewidth is.   The only lecture notes on this that I know of are Philip Klein’s and (stubbornly), I needed something more self-contained – that didn’t build on a course’s worth of notation and background.

So, I prepared these notes on my wiki teaching page.  I don’t prove that k-outerplanar graphs have treewidth 3k-1 or even define treewidth, but I show a simpler version of solving maximum-weight independent set on something I call k-innerplanar graphs.  I think it gives the intuition and ingredients of the full picture without getting caught up in too many details.  If anyone spots a bug, inconsistency, etc, please let me know.

So, yes, basically I am announcing “Ooooh look at me!  I’m doing something everyone else has already done time and time again!”