An Invitation to Coarse Graph Theory

24^th February 2026, 13:00 EEE Building, Elec204
Matthias Kaul
University of Bonn

Abstract

Coarse Graph Theory concerns itself with the geometries obtained from graphs by "zooming out" slightly, i.e. by loosing the ability to distinguish vertices which are at distance less than some parameter d to each other. The first principled study of such geometries was initiated by Mikhael Gromov in the context of geometric group theory.
Recently however there has been renewed attention on these objects from the viewpoint of structural graph theory, trying to transfer well known concepts such as minors, tree decompositions, or planarity into the coarse setting. Shadowing this graph-theoretic development there is also notable interest in reproducing well-known algorithmic results, such as Max-Disjoint s-t-Path (Menger's theorem).

The coarse version of Menger's theorem here says that for a graph G, a distance parameter d, and vertex sets S,T there always exists a k for which one can route k S-T-paths with pairwise distance d, as well as find k balls of diameter O(d) whose removal separates S from T. Nguyen, Scott and Seymour were recently able to show that the coarse analogue of Menger's theorem does not hold in general graphs (arXiv:2508.14332), but a variant thereof does hold for the special case of planar graphs where all terminals are on a single face (arXiv:2509.07174).

We will revisit some of the recent developments in the area, as well as report on some work in progress developing an algorithmic analogue to the result of Nguyen et al.