Associate Professor & College of Engineering Dean's Professor, School of Electrical Engineering and Computer Science, Oregon State University

May 18, 2011

### 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!”

1.   Claire Mathieu — June 1, 2011 @ 6:29 am

Very nice! Thank you!
What do you think of the wikipedia entry on tree width etc?
http://en.wikipedia.org/wiki/Tree_decomposition

2.   Glencora — June 6, 2011 @ 9:02 am

Those are great notes on treewidth – it’s nice to be able to increasingly depend on wikipedia. I initially considered writing up these notes for a wiki entry on PTASes in planar graphs, but didn’t think the level of detail would be appropriate for lecture notes.

3.   Bala Krishnamoorthy — June 15, 2011 @ 5:28 pm

Talking about lecture notes, I’ve been following the model of Robert Ghrist (http://www.math.upenn.edu/~ghrist/notes.html) for a while now. I write on a tablet PC in class (instead of writing on the board), polish to a small extend the scribes after the lectures, and post them as “class notes”. Of course, they’re not as professional as TeX-ed up notes, but they do save me a lot of time. They work okay even when I’m not following a prescribed textbook, e.g., here are the scribes from my graduate level course on integer optimization: http://www.math.wsu.edu/faculty/bkrishna/FilesMath567/S11/LecNotes/welcome.html.

Sorry, the comment form is closed at this time.