Invited Speakers

From planar to 1-planar... or not?

Planar graphs are a well-known and long-studied class of graphs. Lots of properties and results are known, from the famous 4-coloring theorem to the planar separator theorem, with detours into treewidth and bidimensionality. But there are many graphs that, while close to planar in some sense, are not actually planar. Which, if any, of the properties of planar graphs transfer to such "near-planar" graphs? In this talk, I will focus on 1-planar graphs, i.e., on graphs that can be drawn in the plane with at most one crossing per edge. After discussing some general tools to transfer (or not transfer) results from planar graphs to 1-planar graphs, I will focus on some recently obtained results concerning matching, the basis number of the cycle space, and connectivity testing.

CV

Therese Biedl is a professor at University of Waterloo in Canada. She received her Ph.D. from Rutgers University under the supervision of Endre Boros. Her main research interest lies in algorithms for geometric problems, in particular in computational geometry and planar graphs.

Some Tools from Formal Language Theory for Graph Theory

Courcelle's theorem and other similar meta-theorems are now well-known and well-established results in algorithmic community. However, less known are the tools from formal language theory used for proving such theorems and their potentials. Among such tools, Simon's Factorisation Forest Theorem and its extension by Colcombet to trees has been of particular utility the last years. Simon's Factorisation Forest Theorem and its extension by Colcombet has been used by Bojanczyk and Pilipczuk in settling a long-standing open question by Courcelle, and then by Pilipczuk and his co-authors for proving upper bounds on some graph parameters, and recently by Bojanczyk and Ohlmann in proving a weak version of a conjecture by Kwon and I.
The talk will survey some of these results using Forest Factorisation Theorem. The first part is an intermezzo with a monadic second-order characterisation allowing an upper-bound on obstructions. The second part will introduce Simon's Factorisation Theorem and its extension to trees. In a third part of the talk, we will survey three of its uses: how to define a decomposition in monadic second-order logic, the polynomial χ-boundedness of graphs of bounded (linear) clique-width, and a recent result proving that k-labeled well-quasi-ordering is equivalent to labeled well-quasi-ordering on graphs of linear clique-width.

CV

Mamadou Kanté is a professor at Université Clermont Auvergne, Clermont Auvergne INP in France. He received his Ph.D. from LaBRI (Bordeaux, France under the supervision of Bruno Courcelle. His main research interest lies in structural decompositions and associated width measures, listing problems, and convexity problems.