Research Interests

Graph Minors

The theory of graph minors is one of the most developed fields of graph theory. In particular, the graph minors series of Robertson and Seymour has created an extreme growth in the development of graph theory as a whole. It has found both algorithmic and structural applications and revealed a deep link between the theory of graph minors and topology.

Topics I am interested in include

  • width measures like treewidth which are related to graph minors

  • refinements of the Robertson & Seymour structure theory, and

  • the phenomenon of universal obstructions

Matching Theory

There exists an analogue of the theory of graph minors for graphs with perfect matchings. In particular one can generalise the notion of treewidth to this setting. I am interested to see how much of the graph minor theory developed by Robertson and Seymour can be replicated in the setting of matching covered (bipartite) graphs.

Topics I am interested in include

  • the perfect matching width of bipartite matching covered graphs, in particular characterisations, duality theorems and unavoidable matching minors,

  • counting perfect matchings and computing the permanent and

  • Pfaffian orientations and their relation to non-even (bi)directed graphs.

Structural Digraph Theory

The study of forbidden minors for undirected graphs has given rise to many nice and powerful results. The directed analogue however appears to be underdeveloped. One big reason behind this seems to be a severe lack of methods to handle the unavoidable antichains that occur in the study of so called butterfly minors. My aim here is to adapt and develop new methods in order to help establish a richer theory of minors for directed graphs.

Topics I am interested in include

  • directed treewidth, in particular characterisations, duality theorems and unavoidable butterfly minors,

  • possible extensions of the Robertson & Seymour structure theory to digraphs, and

  • the structure of directed cycles, and linkages in digraphs.