Last week I was attending the 43rd (!) International Workshop on Graph-Theoretic Concepts in Computer Science. The workshop took place in Heeze, NL which is a small town not far away from Eindhoven. The conference venue was a more remote hotel. 31 papers were presented in the workshop and we had 3 invited lectures. I will give you a short report on a few things that I found interesting.
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.
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.