Dense but sparse: Graphs of low complexity

Felix Reidl (Royal Holloway, London)

When: Monday September 25, 2 pm

Where: room C417

Abstract

The theory of structurally sparse graphs has provided us with a large array of algorithmic techniques, some of which have been translated to corresponding dense classes. However, these known results have been confined to rather small classes.

Very recent (and still unpublished) results now finally hint towards a comprehensive theory of dense graphs that have a sparse underlying structure. While a full characterisation is still out of reach, we will survey the available puzzle pieces in this talk and discuss what directions future research could take.