This workshop will be held online, over Zoom.
It will be a one-day workshop, consisting of 6 invited talks, and finishing with a session for further discussion and open problems.
For the final session of the workshop, we invite short presentations that highlight an open problem or potential area for future research. If you wish to have a 10-minute slot in our workshop please send an email with a title and short description to a.munaro@qub.ac.uk.
All times are in the Central European Summer Timezone (CEST), UTC+2, GMT+2.
9.30-10.15: David Wood – "The structure of planar graphs"David R. Wood – "The structure of planar graphs"
This talk is about graph structures that (potentially) are useful in algorithmic applications. The focus is on planar graphs, but many of the results hold for more general graph classes. The starting point is the Lipton-Tarjan separator theorem, followed by Baker's decomposition of a planar graph into layers with bounded treewidth. I will then move onto layered treewidth, which is a more global version of Baker's decomposition. Finally, I will introduce row treewidth, which is a refinement of layered treewidth. Dujmović et al [JACM '20] proved that planar graphs have bounded row treewidth. This result has been the key to solving several open problems, and is ripe for algorithmic applications.
Jan Arne Telle – "On Parameters in the Mim-width Family"
Mim-width is a parameter introduced by Vatshelle in his PhD thesis of 2012. In this talk we give a brief introduction to mim-width, comparing it to other width parameters, discussing graph classes of bounded mim-width and also algorithmic applications. We mention also sim-width which is bounded on larger graph classes like chordal graphs, and bi-mim-width that is used for directed graphs.
Eunjung Kim – "Twin-width and Friends"
Twin-width is a graph invariant which measures a distance to a cograph.
Since its recent introduction in [Bonnet et al., FOCS '20], it turned out that twin-width has surprisingly versatile structure: it admits
an efficient FO-model checking, remains robust under FO-transduction, allows simple and natural dynamic programming algorithms,
and a class of bounded twin-width graphs is small, χ-bounded, equivalent to a proper permutation class under FO-transduction, and the list goes on.
The notion of twin-width naturally extends to digraphs and binary structures in general.
Many well-studied graph classes are known to have bounded twin-width including minor-closed classes, bounded rank-width graphs, unit interval graphs and map graphs,
permutation graphs avoiding a fixed pattern and so on.
In this talk, we introduce the notion of twin-width and basic results about twin-width. Then we present a recent development on how known graph classes such as
graphs of bounded path-width, tree-width and rank-width as well as minor-closed classes can be characterized using some natural variants of twin-width.
Vadim Lozin – "A parametric approach to hereditary classes of graphs"
The world of hereditary classes is rich and diverse, and it contains a variety of classes of theoretical or practical importance. Thousands of results in the literature have been devoted to individual classes and only few of them analyze the universe of hereditary classes as a whole. We explore this universe by means of graph parameters. With each parameter we associate the family of hereditary classes, where this parameter is bounded by a constant, and characterize this family by means of critical classes. In particular, we obtain a complete parametric description of the bottom of the universe of hereditary classes, up to classes of bounded neighbourhood diversity. We also obtain a description in terms of critical classes for a variety of other parameters, such as tree-width, tree-depth, h-index, VC-dimension, etc.
Paweł Rzążewski – "The advantages of being modest: subexponential- and quasipolynomial-time algorithms for H-free graphs"
The classical notion of tractability involves the existence of a polynomial-time algorithm for a given problem. However, there are many notorious problems for which we do not know such algorithms, with Independent Set in Pt-free graphs as a prominent example. It appears that some interesting results can be obtained if we are more modest and ask for subexponential-time or quasipolynomial-time algorithms. In the talk we survey recent exciting developments in the area, point out the important methods, and discuss possible directions for future research.
Lalla Mouatadid – "Measuring Linear Structure on Graphs"
We introduce a new graph parameter (LexCycle) that, we believe, measures the linear structure exhibited by various graph classes. LexCycle is based on multi-LexBFS traversals. In this talk, we'll briefly cover how graph searching has successfully been used to extract structural and algorithmic results on certain graph classes that seem to share a notion of linearity. We'll exhibit this linear structure in various classes (from perfect: cocomparability, to not so perfect: AT-free), and prove fixed point type theorems for LexBFS.
Flavia Bonomo
University of Buenos Aires
Buenos Aires, Argentina
Nick Brettell
Victoria University of Wellington
Wellington, New Zealand
Andrea Munaro
Queen's University Belfast
Belfast, UK
Daniel Paulusma
Durham University
Durham, UK