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.
Let me start with the invited lectures.
The first invited lecture was given by Petra Mutzel. Petra talked about crossing minimization in graph drawing. Although we have very decent tools for drawing planar graphs, only a few techniques for drawing nonplanar graphs are known. On the positive side, many graphs from real word examples are almost planar. The idea is then to find a small set of edges whose removal makes the graph planar. Now the graph can be drawn with an algorithm for planar graphs and the missing edges can added back. Quite a few examples were shown were this proposed workflow gave nice results. The problem is how to find the small set of edges (a hard problem). Some ideas were discussed how to get a practical solution here.
The second talk was given by Remco van der Hofstad. Remco talked about stochastic models for graphs. This was a very interesting talk, because I learned a lot about stochastic models and their motivation. Many real world graphs (think about social networks) behave quite differently compared to a random graphs sampled over the set of all graphs. In particular, we can observe interesting phenomena about the degree distribution and the diameter. In social networks the average degree should be bounded by a constant and the maximal degree becomes unbounded for growing network size (heavy tail). Certain models can mimic this behavior, for example the configuration model, which has many nice properties. The invited talk gave a good introduction to this field.
The third invited talk was given by Fedor V. Fomin. Also this talk was quite interesting. The take-home message was that treewidth and fill-in can be computed in polynomial time for graph classes with a bounded number of minimal separators. This I found a bit surprising. But maybe even more surprising is that many graph classes have this property (chordal, circle, trapezoid, ...). An interesting open question is to bound the maximum number of minimal separators for graphs. Currently the best lower bound is while the best upper bound is .
I liked all three invited talks very much. From the plenary talks I wanted to highlight 3 talks, which I found interesting.
- Jean Cardinal gave a talk about Intersection graphs of rays and grounded segments (joint work with Stefan Felsner, Tillmann Miltzow, Casey Tompkins and Birgit Vogtenhuber). Intersection graphs are graphs that have a representation with one geometric object per vertex such that there is an edge between two vertices if and only if the corresponding objects intersect. Depending on the type of geometric objects you allow you will get a different class of graphs. The relationship between some of these graph classes was settled by the authors. For example, not every intersection graph of rays is an intersection graph of downward pointing rays. Jean also talked a bit about the complexity class (existential theory of the reals). This class contains NP but it is not unlikely that it is a proper superset. The recognition and stretchability problems for the intersection graphs considered in this talk were all shown to be -complete.
- Patrizio Angelini talked about On the relationship between k-planar and k-quasi planar graphs (joint work with many authors). A k-planar graph is a graph that can be drawn such that every edge is crossed at most k times (these drawings are simple topological drawings, so edges are drawn as curves). On the other hand, a k-quasi planar graph is a graph where no k edges pairwise intersect. There was quite some work done for these graph classes. One of the main question here is how dense these graphs can get. Patrizio proved that every k-planar graph is also a (k+1)-quasi planar graph. The proof is basically a strategy how to redraw a k-planar graph to get a (k+1)-quasi planar drawing. The strategy uses some nice tricks. The result in the paper was for only, but very recently it was generalized. Hoffmann and Tóth showed that every 2-planar graph is 3-quasiplanar.
- Another interesting talk was given by Bartosz Walczak about Extending Partial Representations of Trapezoid Graphs (joint work with Tomasz Krawczyk). A trapezoid graph is an intersection graph of trapezoids whose bases are drawn at two parallel lines. It is efficiently computable if a graph is a trapezoid graph, but it was open if the more general extension problem can be solved in polynomial time as well. For the extension problem parts of the representation are prescribed. Bartosz showed that this problem can be decided in polynomial time. The key idea is to apply a normalization step. Reverting the normalization is tricky, but it can be achieved with a 2-SAT formulation. The overall running time is . The class of trapezoid graphs was one of two more prominent graph classes for which the complexity of the extension problem was open. The other class was (and still is) the class of circular arc intersection graphs.
The best paper award went to The hardness of embedding grids and walls by Yijia Chen, Martin Grohe and Bingkai Lin. The best student paper award was split between Dušan Knop, Martin Koutecky, Tomáš Masařík and Tomáš Toufar (paper: Simplified algorithmic metatheorems beyond MSO: Treewidth and neighborhood diversity) and Steven Chaplick, Martin Töpfer, Jan Voborník and Peter Zeman (paper: On H-topological intersection graphs). Not all authors have to be students to qualify for the best student paper award.
Usually there is no public business meeting at the WG. But I heard that the steering committee agreed on that, starting from next year's WG, there will be a public business meeting. I am really positive about this decision. By the way, WG 2018 will take place in Lübbenau, Germany from Juli 27 - 29. Nice place.