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.
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.
Many people might be at the
Copacabana SoCG these days. I, however, went to Lübeck to this year's Workshop on Graph-Theoretic Concepts in CS. Today is already the last day of the conference. I have never been in Lübeck before. The city is really nice, definitely worth a visit. The conference site is a hotel, which I usually don't like that much. However, this time it is really well-managed by the hotel.
Let me start with the invited talks. I have seen only two of the three talks. The last talk by Feodor Dragan will be given later today. I enjoyed the invited talks very much. The first was given by Ola Svensson about graph-TSP. Ola has received the best paper award at last year's FOCS for its paper and the result is indeed very nice. The Christofides heuristic is still the best known approximation algorithm for general (symmetric) TSP. This classic approach gives an 1.5-approximation, however, it is widely believed that the Held-Karp LP-relaxation gives a 4/3-approximation. A special version of TSP is graph-TSP, that is TSP with a distance function that is defined via distances in a graph. Not long ago, nothing special was known about approximating graph-TSP. The first (slight) improvement was due to Oveis et al. (2010). The idea here was to modify Christofides approach, such that the the spanning tree is cleverly sampled, instead of taking the MST. Completely other ideas were used by Ola and his co-author to get a better approximation. The key idea is that one can find a set of matchings in a subcubic graph, such that every edge is contained in the same number of matchings. The tour is then obtained by taking a matching and combine it with a spanning tree. The crucial idea is now, that instead of adding edges, sometimes edges can be deleted in the "combination" part. Moreover, instead of a spanning tree one can work with a sparser structure that certifies the connectedness of the tour. This gives rise to a 1.461-approximation. This technique was recently refined by Mucha (1.44-approximation). The current best approximation algorithm is due to Sebö and Vygen (2012) (1.4-approximation) it uses also some other ideas. In particular, it uses ear decompositions. It doesn't seem likely that this is the end of the story for graph-TSP. Continue reading
The second day also had some very nice talks. Probably the talk I was looking most forward to was the talk of Stefan Felsner about "Exploiting Air Pressure to Map Floorplans on Point Sets". A floorplan is a dissection of a rectangle into smaller rectangles. All rectangles are axis aligned. The floorplan is realized on a point set, if every segment contains exactly one point of the point set. Stefan showed that for every floorplan, you can find a realization of an equivalent floorplan on every point set in general position. This is not only a nice result, Stefan used also some cool tools to prove it.
Another talk I liked was given by Nieke Aerts about "Straight Line Triangle Representation" (joint work with Stefan Felsner). Nieke talked about the following problem: Can I draw a planar graph, such that every face has the form of a triangle? To realize such drawings many vertices have to be adjacent to an angle of exactly 180°. The talk was about necessary and sufficient conditions that such drawings exist. There are still many open questions left. This problem seems related to the stretchability of combinatorial pseudo-triangulations, but the straight line triangle representations are more difficult to understand - at least for now.
The second invited talk was given by James McLurkin. James talked about geometric challenges in multi-robot systems and showed many nice videos.
This post is about the European Workshop on Computational Geometry, number 29. This year's workshop takes place in Braunschweig Brunswick, Germany. In case you are interested, there is a book of abstracts ready for download.
The first day had already some very interesting talks. For those of you who don't know, the EuroCG has parallel tracks, so unfortunately, I missed some of the talks. Here is a small selection of talks I found especially interesting (form my very personal perspective):