Graph Drawing 2015 in Los Angeles

This years Conference on Graph Drawing and Network Visualization took  place in Los Angeles last week. In this post I try to give a short summary of my impressions.

The conference was as always very enjoyable. Following the tradition there were two invited talks. The first one was giving by Herbert Edelsbrunner. Herbert gave a talk about “Shape, Homology, Persistence, and Stability”. Over the last years I have heard at least two talks about this topic by Herbert but I always learn something new. The second invited talk was given by Kwan-Liu Ma who is from the Infovis community. This talk was very entertaining, especially the part about the tree metaphor for displaying social contacts.

I also want to highlight a few plenary talks (of course many other were also interesting, check out the list of accepted papers with abstracts).

  • Therese Biedl gave a talk on Small-Area Orthogonal Drawings of 3-Connected Graphs (joint work with Jens Schmidt). This talk was about improving the constant for the area needed to draw a 3-connected graph orthogonally. It was very interesting to see an application of the Mondshein sequence in graph drawing. The Mondshein sequence is a incremental construction for 3-connected graphs, which is surprisingly similar to the more famous canonical order, which is defined for planar 3-connected graphs.
  • Maarten Löffler gave a talk on Linear-size Universal Point Sets for One-bend Drawings (joint work with and Csaba D. Tóth). Here, a very simple and elegant construction was shown how to define a linear-sized point set on which every planar graph can be embedded using at most one bend per edge. Finding a subquadratic point set for the no-bend question is definitely one of the most intriguing open problem in graph drawing.
  • Fabian Lipp gave a talk on Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition (joint work with Alexander Wolff and Johannes Zink). This paper studies the idea to use a well-separated simple pair decomposition (wspd) to approximate some force-directed layout. Usually quadtrees are used to speed up the incremental step in the layout algorithm from O(n^2) to O(n \log n). Fabian showed that one can also use the wspd. Somehow surprisingly this approach has proven (in experiments) to be faster while producing results with good quality. 
  • I also liked the talk given by Benjamin Niedermann  On the Readability of Boundary Labeling (joint work with Lukas Barth, Andreas Gemsa and Martin Nöllenburg). Having recently done a user study by myself I can appreciate the effort to make such a study the right way. Benjamin talked about boundary labelings for maps. There exist several models how to draw the connections (called leaders) from the point sites of the map to their boundary labels. The study investigated which styles are most helpful. Interestingly, the most helpful style for performing tracing tasks (leader is a horizontal + vertical segment) was not considered the most preferred style (leader is a diagonal + horizontal segment).

The conference also had two best paper awards; one for each track. For the track 1 (Combinatorial and algorithmic aspects) the award was given to the paper on Drawing graphs using a small number of obstacles by Martin Balko, Josef Cibulka and Pavel Valtr. The award was well-deserved since the paper contains strong and interesting results. The best presentation award was received by Maarten Löffler who was presenting a paper I was coauthoring. See here for the other awards.

As in every year there was the graph drawing contest. The contest organizers did an excellent job by picking good contest graphs for the offsite challenge. One of the graph, was the graph of all planar graph classes (winning submission by Tamara Mchedlidze) the other was the tic-tac-toe configuration graph. There was a very beautiful submission (well-deserved  winner) for the tic-toc-toe graph done by Jennifer Hood and Pat Morin that was highlighting paths for winning and losing configurations.

At the business meeting we were informed that the steering committee agreed on a new 5 year contact with Springer. There was some discussion last year, whether future proceedings should be published in LIPIcs or Springer or some other place. Changing the publisher or not was and still is a controversial question in the community. Another discussion that came up was if we want to change the current structure of the steering committee (see here for the current status).  I personally would prefer to  have a meaningful fraction of community elected member in the sc. Lets see where this is going. The next Graph Drawing will be in Athens, Greece followed by Boston in 2017. The program committee chairs for 2016 (Yifan Hu and Martin Nöllenburg) plan to require to submit all accepted papers to arXiv.

Overall it was nice to see so many familiar faces. Thanks for the organizer and participants for the enjoyable conference.

Leave a Reply