Last week I attended the Graph Drawing conference in the wonderful city of Bordeaux, France. The conference was smoothly organized, they had sensational food and we had 30°C sunny weather. All lunches and the conference dinner were organized as buffets without seating. I enjoyed this very much, since I was able to meet much more people than in the usual setting. So thanks a lot for the organizers for hosting a great conference.
As usual the conference went for 3 days. Instead of 2 invited talks there were 3 invited speakers this years. The first speaker was Tamara Munzer. Tamara was speaking about research in information visualization. She showed that research in visualization is not only concerned with the design of algorithms, but also with the development of techniques and other things. The central topic of the talk was the usage of space in visualizations.
The second invited talk was given by Emo Welzl. Emo was talking about counting and enumerating of crossing-free structures. I liked his talk very much, not only since I am also working on these problems. Emo presented a bound for the maximum number of simple cycles on a point sets. This work (joint work with Micha Sharir and Adam Sheffer) builds on a very clever application of a weighted version of Kastelyn's theorem for counting perfect matchings with Pfaffian orientations. Emo also presented as a new result an algorithm for counting the number of crossing-free perfect matchings on point sets with polynomially delay (joint work with Manuel Wettstein). The counting algorithm builds on the framework of Alvarez and Seidel for counting triangulations, however it is more tricky to count (noncrossing) perfect matchings, since every crossing-free graph can be completed to a triangulation, but not always to a perfect matching.
The third invited talk was given by Joe Marks, who was vice president and research fellow at Disney Research. In this very entertaining talk Joe presented a large number of projects they did at Disney Research. Most of the problems had a computer graphics background. It was interesting to see what kind of (fun) projects are done in industry.
There were also a number of great contributed talk. Let me a list a few of them (see also here for a blog post by David Eppstein about GD in Bordeaux in which he discusses a few interesting talk which I wont repeat):
- Michael Bannister gave a talk about Superpatterns and Universal Point Sets (joint work with Cheng, Devanny, and Eppstein). Finding a set of points of order on which every planar graph with n vertices can be embedded is an intriguing open problem. Such a point set is called a universal point set for planar graphs. Michael presented a new bound of size for a universal point set. More interesting that the actual improvement is the application of a novel technique. The authors reduced the problem to finding a superpattern that contains all possible permutations of [n]. In fact only permutations avoiding 213 do matter. It was then shown how to get a small superpattern that implies the improved bound. The technique might be applicable to get further improvements. Michael won the best presentation award for his nice talk.
- Robert Krug from the Tübingen Group spoke about Slanted Orthogonal Drawings. He proposed an octilinear poly-line drawing scheme that can deal with crossings. Crossings are however limited to slanted (neither horizontal or vertical) segments, and incident edges meet only at endpoints of horizontal or vertical segments. I found these drawings very appealing. Robert presented an LP-formulation that tries to find a planar solution. It is however an open problem if such a solution always exists.
- The last talk I want to mention was Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity, given by David Eppstein. The talk started with an explanation of the game planarity, in which you have to untangle a circular layout such that all crossings are removed. Surprisingly, you can draw the final results always in a grid-like fashion, which is not true for general planar graphs. The reason for this lies behind the algorithm that constructs the graphs for the game. These graphs are in fact 1-skeleta of line arrangements. David exploited a relationship between such graphs and grid-like layouts. It also helped to come up with an easy algorithm to solve the game. Of course there are well-known linear algorithm for laying out a planar graph, however David's method is easier to do "by hand".
Next GD will be in Würzburg, Germany, organized by Alexander Wolff.