Report from GD2016

Last week I was in Athens attending the 24th Symposium on Graph Drawing and Network Visualization. I will give a short report on what happened in Greece.

As usual there were about 40+ talks (2 of them were invited talks), a poster session and an onsite contest. Let me start with the talks. The program can be accessed here. You can download the whole proceedings on this webpage, since (almost) every contribution was crossposted on arxiv. This was the first time that this policy was enforced, and I think it is good step towards the right direction to have open access proceedings. There were quite a few interesting talks. I want to highlight three of them.

  • Martin Gronemann was talking about Bitonic st-orderings for Upward Planar Graphs. Martin talked how to combine ideas from canonical orderings of planar graphs and st-orderings of directed graphs. Simply speaking, one cannot expect that an st-ordering will have the same nice properties as a canonical order. However, if we have a bitonic st-order we can use this to compute an upward planar drawing on a grid. He then presented a linear time algorithm that finds such a bitonic st-ordering. If none exists it computes a minimum set of edges such that after splitting those edges the graph has a bitonic st-ordering. The ordering can then be used to compute an upward planar drawing on an O(n)\times O(n)O(n)\times O(n) grid with at most one bend per edge and at most n-3n-3 bends in total. This talk won the best presentation award selected by the conference participants.
  • Andrew Suk (joint work with Jacob Fox and Janos Pach)  presented an algorithm for approximating the rectilinear crossing number. The rectilinear crossing number of a graph is the minimal number of crossings of a drawing of this graph with straight-line edges. Computing this number is known to be a hard problem. The authors attack the problem by partitioning the graph into “regular” subsets, which exists due to the Frieze–Kannan regularity lemma. The partition induces another (weighted) graph which is drawn first. Then each set of the partition will be added back. This yields an algorithm that runs in almost quadratic time and generates a drawing that uses not more than o(n^4)o(n^4) crossings compared to the minimum-crossing drawing. Thus, for dense graphs this gives an 1+o(1)1+o(1) approximation.
  • Martin Fink talked about Block Crossings in Storyline Visualizations (joint work Thomas C. Van Dijk, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alex Ravsky, Subhash Suri and Alexander Wolff). Storyline drawings were popularized by a famous xkcd comic. During the last years quite a few papers were published about how to compute these visualizations. On desirable feature is of course to have few crossings. In this work the authors aimed at minimizing block-crossings. If a set of parallel running lines is crossed by another set of parallel running lines this might give many crossings, but it is counted as a single block crossing only. It is shown that minimizing the number of block crossings is a hard problem. The authors give a quite involved approximation algorithm that reduces the problem to a problem on interval hypergraphs. The approximation  algorithm is not practical at all, but from a theoretical perspective it is quite interesting. The paper also includes an FPT-algorithm and a heuristic greedy algorithm. This contribution received the best paper award for the Theory track selected by the program committee.

As usual there there were two invited talks. The first invited speaker was Roger Wattenhofer who talked about Distributed Computing: Graph Drawing Unplugged. In his talked he presented several applications that could benefit from better graph drawing algorithms. One example was about visualizing a (network?) of music recommendations as a graph without edges. He also talked about the role about unit disk graphs and quasi unit disk graphs in wireless computing. The second invited speaker was Daniel Keim. He gave a very interesting talk explaining his work in visual analytics. In his talk he gave many interesting examples (soccer player paths, flight routes, network traffic data). He claimed that fully automated graph drawing only works under certain preconditions, which are in general not clear or not given. This seems indeed true and I think he made a few very good points.

The graph drawing contest had an interesting offsite challenge. One task was to draw the graph of the family tree of the greek goods and the other task was to draw a network derived from the Panama paper data. You might check out the contest webpage to see the results including the winning contributions. I liked the winning drawing of the greek gods family tree by Jonathan Klawitter and Tamara Mchedlidze most (beautiful iconography), but also the other submissions were very nice. There were also two onsite challenges in the manual and automatic category  – check out the website for details and winner.

Last but not least I will include a few details from the business meeting. The conference had 99 participants. The PC chairs reported that there have been 99 papers submitted, from which 44 were accepted. This was the second highest number of submissions for a graph drawing conference. There were two tracks (theory/applied) and two paper versions (regular/short). It was the first year when arxiv cross-postings were enforced. This process was relatively smooth, with a few exceptions (papers that already had an extended arxiv version). We had no big discussions this year. Next GD will be held in Boston – PC chairs will be Fabrizio Frati and Kwan-Liu Ma.  The dates are not settled yet (but the conference will be held at the end of September). It was also announced that GD18 will be held in Barcelona.

Abby Singer/Songwriter 2017 movie streaming

Leave a Reply