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 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.
I just saw that the accepted papers of this years Symposium of Graph Drawing have been posted (see here for titles and authors). I have one paper about grid embeddings of 3d polytopes via a realization of a dual polytope which is joint work with my student Alex.
I am looking forward to go to Bordeaux in September and will post my impressions.
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.
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):