The list of papers accepted to ISAAC 2009, the 20th International Symposium on Algorithms and Computation is now online. (I'd be happier if abstracts were also included, but they're not.)

I never had any thoughts of going to this one, but my colleague and frequent co-author Mike Goodrich has been excited about the possibility of a trip to Hawaii for months, and now he has a good excuse to go. He and his student Darren Strash have a paper there on succinct greedy embedding of planar graphs into the Euclidean plane (related to our previous work on greedy hyperbolic embedding). The idea is to use a version of the Leighton-Moitra embedding from FOCS 2008 (for 3-connected planar graphs, or more generally graphs containing an appropriate cactus subgraph) and show how to compute O(log n)-bit labels for the vertices in such a way that the embedded location of each vertex is a function (independent of the graph) of its label. In this way they get around the “cheating” aspect of much of the greedy embedding literature, that a single vertex location already encodes enough information by itself to represent an entire routing table.

Another result that I've heard of before, mentioned briefly in Erik Demaine's invited talk at WADS, is his paper (listing his last name as author twice in his usual egocentric style, also with Konjevodz and famed origamist Robert Lang) “Folding a Better Checkerboard”. If I remember correctly, they save a factor of two in the area of the starting sheet of origami paper (with different colors on its two sides) needed to fold a checkerboard of a given size (in which the two colors alternate to form an 8×8 grid of squares).

There are many more titles that look interesting to me but that I don't know a lot more about than the title itself. I'm sure it will be an interesting conference, and if you haven't already done your planning for Hawaii in December, now would be a good time.