After the final day of Graph Drawing, the conference organizers arranged a guided tour for us at ZKM, a large modern art museum in Karlsruhe with a big exhibit of algorithmic and interactive art, and what they told us was the world's oldest continuously-operating computer, originally built using vacuum tubes by Konrad Zuse. Definitely worth a visit — I would have liked a lot more time to browse the exhibits.

Several of today's talks were a bit of a blast from the past for me, discussing results related to geometric thickness and confluent drawing.

( Read more... )

Just in time for Graph Drawing, I've updated my page on geometric thickness to reflect an exciting new result of Barát, Matoušek, and Wood: bounded degree graphs may have unbounded geometric thickness, even approaching the square root of the number of vertices. This is in strong contrast to my SoCG 2004 paper with Duncan and Kobourov, which showed that degree four graphs have bounded geometric thickness.

The basic idea seems very simple, but nonconstructive: use counting arguments to compare the numbers of bounded degree graphs and low thickness graphs. For low bounds on the geometric thickness, there are few enough order types of point sets, and few enough ways of connecting the points in an order type into a small number of planar-straight-line layers, that not all bounded degree graphs can have a low-thickness representation. The authors also apply the same basic idea to some related problems of drawing with few edge slopes.