Invited talks

One of the many breakthrough results originating from Robertson and Seymour's Graph Minor Series is the Graph Minor Algorithm which allows for efficient minor checking as well as providing an FPT-algorithm for the k-Disjoint Paths Problem. At the core of this problem lies the celebrated Irrelevant Vertex Technique whose proof of correctness heavily relies on a deep structural insight: The existence of the so-called Vital Linkage Function λ. Robertson and Seymour proved that any instance of the k-Disjoint Paths Problem with a unique solution using all vertices of the graph must have treewidth at most λ(k). The original proof did not make any estimate on the order of λ and the best bound until now is still estimated - yet never explicitly stated - to be at least quadruple exponential in k.

In this talk I give insights to how recent developments in the theory of graph minors may be used to prove that λ(k) is exponential in kO(1). Indeed, we prove a stronger version of the Vital Linkage Theorem as follows: Let k be the number of terminals, b be the bidimensionality of the terminal set, and d be a non-negative integer, then there exists an integer β(k,b,d) ∊ exp( (b+d)O(1) ) kO(1) such that every instance of the d-folio problem with k terminals and treewidth at least β(k,b,d) admits an irrelevant vertex. These bounds are optimal up to the degrees of the polynomials involved and imply an algorithm for the rooted minor checking problem for minors of size at most d with running time 2β(k,b,d) n2.

This is joint work with Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer, and Dimitrios Thilikos.

Coarse graph theory is an emerging area in the intersection of (structural) graph theory and (coarse) geometry. Its overall aim is to analyse the `coarse’ or `large-scale’ structure of a graph. I will begin with a short introduction to coarse graph theory and then discuss a coarse analogue of the Erdős-Pósa theorem. The classical result states that there exists a function g such that, for every graph G, either G contains n disjoint cycles (i.e. n·K_3 is a minor of G), or there exists a set X of at most g(n) vertices of G such that X meets all cycles in G (i.e. G-X is a forest). 

In the coarse setting, disjoint cycles are replaced by K-fat minor models of K_3 that are pairwise at distance at least K. I will describe a result showing that in the absence of n such models, the graph G is f(K)-quasi-isometric to a graph H containing a set X of at most g(n) vertices such that H-X is a forest.

I will also discuss an equivalent formulation in terms of bounded-radius balls meeting all K-fat minor models of K_3 in G.
This is joint work with Marthe Bonamy, Romain Bourneuf, and James Davies. 

Adjacency labeling schemes provide a local representation of graphs: each vertex is assigned a short label, and adjacency between two vertices can be determined solely from their labels. In this talk, I will survey recent advances in adjacency labeling schemes, with a particular emphasis on small graph classes. I will highlight new positive results that establish efficient labeling schemes for broad families of such classes, as well as recent lower bounds that reveal fundamental limitations of these representations. The talk will outline several directions for future work.