Tag Archives: planar graphs

TSP in 1-planar graphs

I recently came back from a Dagstuhl I organized with Phil, Claire and Daniel on optimization algorithms for planar graphs.  I think I finally caught up for the week away and sat down this afternoon to think about research.  A problem suggested at the workshop was TSP in 1-planar graphs.  1-planar graphs are those graphs that can be drawn in the plane such that any edge has at most one other edge crossing it.

We have PTASes for TSP in bounded-genus graphs and in particular, these PTASes solve the subset TSP problem wherein you want to find the shortest tour that visits an input subset of vertices.  In general graphs, we would just take the metric completion (create the complete graph on that input subset of vertices where the weight of each edge is the length of the shortest path in the original graph) and solve the problem in that completion.  In planar graphs you could do this, but you would lose planarity.  The subset version is inherently interesting: if you are designing a delivery route, you definitely don’t want to visit every intersection in your region.

One would suppose that for 1-planar graphs, one would also want to give a PTAS for the subset version of the problem.  However, we can argue that isn’t the case.  Take a general graph G and consider any drawing of that graph in the plane.  An edge in this drawing will have any number of other edges crossing it, creating a sequence of crossing points along the edge.  Subdivide this edge by introducing a vertex between every consecutive crossing point and distribute the weight of the original edge among these new edges.  Now you have a 1-planar graph H.  If you could find a (1+eps)-approximate tour that visits the subset of vertices that correspond to the vertices of G, this ordering of vertices would correspond to a (1+eps)-approximate tour in G.  However, metric TSP is APX-hard.  So, there can’t be a PTAS for subset TSP in 1-planar graphs.

There might still be a PTAS for TSP (visiting all the vertices) in 1-planar graphs.  This doesn’t seem as interesting a problem though.

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

Experience Theory Project and Prezi

I’m participating in the Experience Theory Project at the University of Washington right now.

ETP is an event for undergraduates with talent and interest in theoretical computer science, sponsored by the theory groups at the University of Washington and Microsoft Research. The purpose of the event is to exchange ideas about exciting results and research directions in theoretical computer science, and enjoy Seattle in all its summer glory.

Anna Karlin is organizing and asked me to join in.  It’s a great group of students and a great excuse to spend some time at UW and MSR.  There have been about 15 technical talks aimed at senior-year, bright undergrads.1 In an attempt to minimize the time I spend designing talks, I used a new presentation method – Prezi.  I’ve used it before and was perhaps a little too excited about it. As critics would point out, I didn’t take full advantage of Prezi:  I designed this poster2 in Illustrator with a tablet, exported to Prezi as swf and then added “frames” in order to navigate around the poster.  Why?  Prezi was frustrating to work with, figures would have to be uploaded one by one, jpegs cannot be uploaded in high enough resolution to zoom in on, uploading a pdf plain failed.  I was worried about (lack of) reusability.  At least now I have a reusable poster.

There were a few technical issues: I couldn’t use a remote to run the presentation; I forgot to manually set the “sleep” time on my laptop (accustomed to this being automatically set by Keynote); manual navigation sometimes did unexpected, non-deterministic things.  Prezi was cute and flashy, but I wouldn’t use it for a longer talk or a more technical talk.  Overall, I wouldn’t recommend it.

1 The level of the talks, at least on topics of which I am the least informed, was perfect for me – a gentle introduction.  Disconcerting, maybe.  Perhaps I am just too slow to follow the standard (short) technical talk in our field.
2 Which I hope to print out on a plotter and put up in my department. Look! Pretty pictures!

Job talks

I recently found out that when I gave my job talk at Oregon State University last year, I was being recorded.  I was hesitant to post it, but I hope that, despite this far-from-perfect performance, it might be useful to those on the job market this year.  Note that Oregon State is not a theory school.  I was talking to an audience of grad students and faculty, none of whom (except one) work in algorithms.  If I was giving a talk at a theory powerhouse, I probably would have targeted differently.

I broke a lot of standard rules in giving this job talk.  First and foremost, I did not practice it.  *gasp*  Practice would have removed a lot of my “um”s and “uh”s.  In my defence, when I practice a talk too much, I find it gets stale.  However, practicing it once from start-to-finish would have been a good idea.  In watching this talk (as painful as it is), I think the best thing I could have done was to tape myself once.

Second, I climbed on a chair.  I was offered a laser pointer, but I hate laser pointers.  They are hard to keep steady and the point is very small and hard to see for the audience.  I find it about as useful as the speaker pointing to their laptop screen while they give a presentation.  So, at some point I wanted to point at something that too high for me, so I climbed on a chair.

Another minor thing that I wish I would get in the habit of doing is repeating an asked question. Taking two seconds to summarize the question both confirms that you are answering the intended question and allows the entire audience to hear both the question and the answer.

The slides for the talk are available for Keynote and Powerpoint here.