Fatness, Flatness, and the Semi-half-graph Algorithm

Fat minors are a coarse analogue of the classic minor relation that is suited to the analysis of structure in length spaces: metric spaces equipped with a reasonable notion of shortest paths. We will sketch a proof that length spaces excluding a fixed fat minor enjoy a property we call drill-flatness, which is a metric analogue of the notion of flatness known from Sparsity (the structure theory of sparse graphs). This leads to a bound on eps-scatter dimension --- a metric analogue of semi-ladders from Sparsity --- and to an efficient approximation scheme for the k-Center problem in fat-minor-free length spaces.

The talk will be based of a joint work with Arnold Filtser, Hung Le, Nikolas Mählmann, and Marcin Pilipczuk (https://arxiv.org/abs/2607.21474), but will contain traces of the older joint work with Grzegorz Fabiański, Sebastian Siebertz, and Szymon Toruńczyk (STACS '19).