I was just in Bordeaux, France, for the 21st International Symposium on Graph Drawing. Some highlights:

  • The food, which was uniformly excellent. Or maybe non-uniformly excellent: standouts included macaroons of various flavors, a caramelized puff pastry stuffed with foie gras, very tender scallops drenched in olive oil, an oyster party at the poster session, and of course the wine. The conference lunches and banquet both featured a stand-up buffet, which allowed us to try small bites of lots of dishes rather than having to pick just one, and encouraged more mixing than I've seen with the more usual sit-down arrangement.

  • The invited talks.

    • I learned a lot from Tamara Munzner about how many different channels of information are available when designing an information visualization, and on how to coordinate these channels effectively to convey what you want to convey. It made me realize, for instance, that graph drawing with fixed vertex positions should probably get more attention than it does, because the position channel is one of the most important but (in drawings where it is used mainly to make the layout look nice) one of the least effectively used. Relatedly, Chan et al had a nice fixed-vertex-position paper at the conference, so it doesn't get no attention, just not enough.

    • Emo Welzl had already given a talk at GD 2006 on combinatorial enumeration problems for geometric graphs (a talk that led directly to one of my papers), and here repeated that performance. I was pleasantly surprised how little overlap there was in content between the talks, despite their similar topics.

    • Joe Marks was an old-time graph drawing researcher who became head of research at Disney, and built up a big system of labs there, before spinning off a new market research firm (the similarity in names is not coincidental: he mentioned getting a lot of phone calls at Disney from people thinking he was a market researcher, and learning from them how much more could be done in that area). He described a dozen or so inspiring projects coming out of his years at Disney ranging from technical (e.g. automated methods for in-betweening animations) to social (resurrecting the amusement park ride photo business by combining pay-what-you-want pricing with a half-for-charity kicker). By asking us to predict both their academic value (in citations) and commercial value (in dollars) he made the point that this sort of industrial research can be a good investment in both measures at once.

  • The contributed talks. I've posted here already about some of the papers, including (earlier) my own. Some other talks that caught my attention include:

    • Christopher Auer on a characterization of planar graphs in terms of splittable deque data structures that could lead to simplified planarity testing algorithms and formed the basis of one of the entries in last year's game contest.

    • Nieke Aerts on the graphs that can be drawn so that all faces are triangles (possibly with subdivided edges). She has a combinatorial characterization of these graphs in terms of certain systems of marks (indicating where the 180 degree angles go) but can't yet turn it into an algorithm.

    • Alexander Igamberdiev on embedding convex polyhedra into small integer grids. A big open question in this area is whether all 3d polyhedra can fit into grids of polynomial size, or whether exponential size is necessary. A previous paper by other authors showed that the stacked polyhedra, a very special case of convex polyhedra, do fit into polynomial grids; this paper extends the same result to their duals. The obvious next step would be bounded treewidth. André Schulz (Igamberdiev's co-author) has a related blog posting, on small grid embeddings of the dodecahedron.

    • Stefan Felsner (Aerts' advisor and co-author) on rectangular partitions. Two subdivisions of a rectangle into smaller rectangles (no four meeting at a corner) are (weakly) equivalent if they are formed by the same number of vertical and horizontal line segments with the same pairwise intersections. Felsner used a generalization of area universality to show that, for every subdivision with n segments, and every set of n points in general position, there is an equivalent subdivision in which each point lies on a segment. But, frustratingly, the proof is not constructive: we don't have a provably efficient algorithm for finding this subdivision.

    • Helen Purchase on how many of her previous user-study conclusions were wrong. Or at least, not supported by a follow-on study that attempted to answer the questions from the audience for her previous work of "what happens if you vary this aspect of the experiment?"

    • Maarten Löffler on visualizing two-set Venn diagrams for points with fixed locations, by finding two trees spanning each set whose union is as short as possible, and then using these trees as the skeletons for curves around the sets.

At the business meeting we learned that next year's GD will be in Würzburg, Germany (organized by Sasha Wolff) and that GD 2015 will most likely be in Los Angeles (organized by Csaba Tóth). The distinction between short and long submissions is not working well and will probably be eliminated. And the distinction between theoretical and applied submissions is also not working well but we'll try again to make it work before giving up.

Finally, at the end of the conference we held a vote for the best presentation award, and I'm proud to announce that my student Michael Bannister won, for his presentation on our joint work with Jack Cheng and Will Devanny on superpatterns and universal points sets.

ETA: See also André Schulz's report from the same conference.