In a former post I wrote about the art exhibition "Bending Reality" that took place at Schloss Dagstuhl. The exhibition was part of a workshop about curved graph drawings. I am happy to announce that the organizers have set up a webpage that contains all the exhibits (including the nice metro maps of Maxwell Roberts). One of my favorites is the "Flowerpot" by Günter Rote.
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 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG for short, takes this year place in Lübeck, Germany. Today I found out that their webpage lists the accepted papers (titles and authors but no abstracts).
Fortunately, I also have a paper at this year's WG. The paper is about drawing graphs with circular arcs. Since I never been to WG before I am looking forward to go to a new conference. The list of accepted paper looks actually very interesting - there are quite a few talks about graph drawing and about representation of graphs.
I just heard that Adam Sheffer has a blog called "The Plane Truth - Combinatorial geometry and other typos". Adam writes about algebraic techniques in combinatorial geometry. These techniques lead very recently to new results in the distinct distances problem (see here for the seminal paper by Guth and Katz).
Adam is known for his work on counting geometric graphs. In particular, he and Micha Sharir showed that every point set in the plane with n points contains at most triangulations. Since I am also working on similar problems I hope he also writes about these problems from time to time.
Currently I am at a workshop in Dagstuhl about Drawing Maps and Graphs with Curves. Part of this workshop is the exhibition Bending Reality: Where arc and science meet, which is, well, about drawings of maps and graphs with curved edges. I will write about the exhibition in a different post. Today I concentrate on a series of beautiful drawings of metro network maps by Maxwell J. Roberts, which were shown at the exhibition. Max also gave an interesting talk about the ideas and the motivation behind his drawings. Often one has to distinguish between artistic design criteria and usability. I am mostly interested in these drawings as art, and there were quite a few exceptional drawings presented.
Since the workshop is about curved arcs, also most of the metro maps were using curved edges, quite to the contrary to the prominent octolinear design rule. Here is an example of the network map of Paris. The network in Paris is one of the densest in the world. At the first glimpse I thought that the curved version is a bit chaotic due to the absence of parallel lines. However I find it absolutely plausible, that it is easier to navigate compared to the official Paris map. Maybe most important, the ring formed by the lines 2 and 6 is not very visible in the official map, whereas it is the crucial feature in the curved map. Max claimed that people can navigate on the curved map 50% faster. Still half of the people would prefer the traditional map.
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.