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.

# Tag Archives: wg

# Citation graphs of interconnected communities

As a follow-up to my previous post about the citation graph of the Graph Drawing conference I computed a few more drawings with gephi. This time I have concentrated on visualizing connections between conferences with a similar scope. I improved my "springerlink-crawler". In the current version I first scan all the titles and then I scan for references where the matching is done by title. By this I will also detect references to journal versions if they have the same title. Again the citation graphs are very sparse, since they only reflect citations within the conferences. The data set is very likely not 100% accurate, but my impression is that it is good enough to illustrate a few interesting things.

### Continue reading

# WG 2013 in Lübeck

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

# Accepted Papers for WG 2013

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.