Report from Graph Drawing

I'm currently in the process of returning^* from Würzburg, Germany, where I attended the 22nd International Symposium on Graph Drawing (GD 2014) and was one of the invited speakers at the associated EuroGIGA/CCC Ph.D. school on graph drawing.

The format for the Ph.D. school was three one-hour lectures in the morning and three hours of working on exercises in the afternoon, for two days. My contribution was a high-level overview of graph drawing methods that involve curves (an updated version of my Dagstuhl survey). You'll have to ask one of the students how well the school really went, but my impression is that it was a success. Among other things, it brought in 40 students, and perhaps helped GD itself achieve an unusually high number of participants.

There were two best presentation awards from GD. One went to Vincent Kusters, for a talk on "Column planarity and partial simultaneous geometric embedding" with Evans, Saumell and Speckmann. Their main result is that if one is given two trees on the same vertex set, then it is possible to find planar drawings of them both, with straight line segments as edges, in which a large fraction of the vertices are in the same location in both drawings. (It is not always possible to place all vertices the same in both drawings.) There was also a best poster award, given to Thomas Bläsius, Fabian Klute, Benjamin Niedermann, and Martin Nöllenburg, for their work on "PIGRA", a tool for pixelated graphs. Instead of the usual poster format (a few boxes of text+figures, not very different from the set of slides from a short talk) they made an effort at presenting their work in a graphic-novel format, with a stick-figure narrator that looked like it was inspired by xkcd. There were two good invited talks, by Oswin Aichholzer on some problems related to the crossing numbers of complete graphs and by Jean-Daniel Fekete on visualizations of graphs based on adjacency matrices rather than node-link diagrams, as well as, of course, many interesting contributed talks.

The other best presentation award went to Fidel Barrera-Cruz for his work with Penny Haxell and Anna Lubiw on morphing one triangulation to another by piecewise linear motions while preserving planarity at the intermediate stages. It was one of the few talks to include a demo of things happening dynamically rather than just static images, which worked very well for this topic. I can't find the paper itself online but it seems to also be part of Barrera-Cruz's Ph.D. thesis.

A few of the other talks that were memorable to me:

Wednesday morning, Jan Christoph Athenstädt spoke about making overlaid drawings of two partitions of a set of elements; the same problem can be interpreted as one of drawing a 2-regular hypergraph. It's easy to construct such a drawing by using membership in one partition as an \( x \)-coordinate and in the other partition as a \( y \)-coordinate, and drawing the sets as ovals around the rows and columns of the resulting grid layout, but this is problematic in some respects; for instance, it has empty regions where pairs of sets look like they intersect but actually don't. On the other hand if the partitions are to be drawn as pseudocircles (at most two crossing points per pair, intersecting only as needed) the problem turns into one of graph planarity, but is not always realizable. An intermediate level of constraint on these drawings is unfortunately \( \mathsf{NP} \)-complete to recognize.

On Wednesday afternoon, one of Philipp Kindermann and Fabian Lipp (I no longer remember which) spoke about their work with Sasha Wolff on boundary labeling. If you've ever used the todonotes package in LaTeX, you know what this is: a bunch of rectangular labels (notes to you or your co-authors reminding you of things that need to be changed) are to be placed in the margin of your LaTeX output, connected by "leaders" (polygonal paths) to the point where the change needs to be made. todonotes is a little brainless about how it places its notes and leaders, and their paper discussed an improved system for the same problem. Unfortunately it is implemented in LuaLaTeX, which I am still leery of using. (I don't think arXiv allows it and given the security issues of running a real programming language from user-contributed source code I'm not sure I'd want to advocate that they start; the same is true of the publishers I've worked with.)

Thursday morning had a whole session on 1-planarity, a topic of some interest to me. Di Giacomo, Liotta, and Montecchiani showed that outer-1-planar graphs with maximum degree \( d \) can be drawn with the given embedding using line segments of \( O(d) \) slopes, or planarly (they are always planar graphs) using \( O(d^2) \) slopes, better than the higher polynomial for planar 3-trees and exponential known bound for planar graphs in general. Two additional papers concerned "fan-planar graphs", graphs drawn so that, when an edge is crossed, its crossing edges form a fan (adjacent on the same side to a single vertex). Apparently there is some connection between these graphs and confluent drawings, although I'm a little fuzzy on the details.

Thursday afternoon, in a session including one of my papers on (impractical) algorithms for crossing minimization, we also had a user study presented by Sergei Pupyrev (with Kobourov and Saket) showing that for larger graphs the number of crossings does not seem to be strongly correlated with usability of the drawing. This is in contrast with many past works showing that for smaller graphs crossings are quite important. I'm always glad to see research in this style at GD – I think it helps keep us grounded, when otherwise we have a strong tendency to do theory that has no practical applications – but I can see why it is a bit rare: most of the questions afterwards were actually poorly-disguised complaints "you're doing it wrong". There's always something you could have done differently that might have shown a different result, and always someone who has strong opinions on that particular detail. So it's difficult to get such research accepted and the reactions can be a bit discouraging when it is.

Friday morning Therese Biedl gave another entertaining talk, on transforming one style of drawing into another while preserving its height. But the moral of the story is that height is probably the wrong thing to optimize, at least for straight-line drawings, because of one of her examples: a planar 3-tree which could be drawn in linear area with height five, but required exponential area for its optimal height-four drawing.

And finally one of the Friday afternoon talks also particularly caught my attention. Fabrizio Frati spoke on his work with Dehkordi and Gudmundsson on "increasing-chord graphs", a strengthening of greedy drawings. A path from \( s \) to \( t \) is greedy if the distance to \( t \) monotonically decreases along the path. It is self-approaching if every subpath is greedy in the same direction. And it is increasing-chord if it is self-approaching in both directions. It is unknown whether every point set in the plane forms the vertex set of a planar increasing-chord graph, but Frati and his co-authors showed that every point set can be augmented by a linear number of points so that the augmented set supports such a graph. The proof has two parts: a proof that a triangulation with all acute angles is always increasing-chord, and an old result of mine that every point set has an all-acute Steiner triangulation.

In organizational news: We are soon to have elections for new GD steering committee members, as four members' terms are expiring (Ulrik Brandes, Seok-Hee Hong, Michael Kaufmann, and me). Next year, GD (renamed as the "International Symposium on Graph Drawing and Network Visualization" but with the same numbering and acronym) will be in Northridge, California, with Csaba Tóth organizing. (Csaba looked into instead having it at a nearby beach town but they were too expensive.) After dropping short submissions as a category this year (because of problems in past years where they were judged head-to-head against longer submissions and, unsurprisingly, lost) we will reinstate them next year as "GD notes and demos" with separate reviewing and shorter talks. Along with this year's best poster and best presentation awards, we are reinstating the best paper and test of time awards previously given in 2012; the test of time one will be for papers published in GD between 1994 and 1998 (inclusive). GD 2016 will be in Athens, Greece.

Much German food and wine was served (this is in Franconia, one of Germany's wine-making areas and the home of drier wines than the other parts of Germany), old friends seen again, etc. I enjoyed my trip and am looking forward to a more conveniently-located GD next year.

^*Missed a connection and have to spend the night in Newark.

---

Comments: