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.

The thickness talk came first: Mareike Massow talked about bar 1-visibility graphs: graphs formed by collections of horizontal line segments in the plane, where two line segments are considered adjacent if there is a vertical segment that connects them passing through at most 1 other segment (that's where the 1 in the name comes from). Bar visibility graphs without the pass-through part are planar themselves. Mareike showed that there is a bar 1-visibility graph with thickness three, and conjectured that the thickness of such graphs is always at most three; it is known that the thickness is at most four. She also defined an interesting subclass of these graphs in which all segments have their left endpoint on a common vertical line, and proved that they have thickness two (essentially, the proof is: two-color a Cartesian tree derived from the segments, orient edges from longer segments to shorter ones, and give each edge the color of its source vertex). She asked whether these graphs always have geometric thickness two. Related to geometric thickness were two talks Monday on simultaneous embedding by Alejandro Estrella-Balderrama and Fabrizio Frati; today, Franz Brandenburg came near the topic of simultaneous embedding when talking about partitioning graphs into pairs of trees but unfortunately he quickly dismissed the possibility of using such a partition to find a nice drawing as fruitless.

There should have been three talks related to confluent drawing, but one was cancelled for lack of speakers. Yehuda Koren spoke about several interesting techniques for drawing graphs with the vertices placed around a circle: a Laplacian smoothing technique for reducing the sum of distances of vertices and hence reducing crossings (with some care so that it doesn't converge to a placement where all vertices land on top of each other), a dynamic programming algorithm for finding a maximal outerplanar subgraph respecting the given embedding, to be drawn outside the circle (with all other edges inside), and a technique very similar to confluent drawing in which collections of edges are joined into confluent tracks by an agglomerative hierarchical clustering procedure. These tracks are interpreted differently than in confluent drawing, however: instead of representing a biclique in which all vertices at one end of the track are connected to all at the other, they represent a set of parallel edges in which each vertex at one end of the track is connected to a single vertex at the other, according to its position in the circular sequence of endpoints. He seemed quite excited about the possibility of using the results from our color paper to make the crossing confluent tracks easier to distinguish from each other. The combination of his techniques produced pretty pictures, anyway, though I'd have to see more examples to be convinced that graphs with differing structures result in pictures with differences that can be seen visually. Also, Michael Hirsch spoke on the first empirical comparison of confluent drawing algorithms, showing that they can be effective at removing nonplanarities from some example graphs (but not from the Rome graphs).