Twin-width

The twin-width of a graph, and more generally of a binary structure, has recently been introduced. It is based on a succession of vertex contractions going from the initial graph to a single vertex, called contraction sequence. Surprisingly many classes have bounded twin-width, while generic classes of bounded twin-width enjoy several structural properties and improved algorithms. Throughout applications in algorithmic and structural graph theory, combinatorics, finite model theory, and algebra, we will survey various uses of twin-width. We wish to demonstrate that, perhaps in hindsight, the notion naturally pops up in many contexts. Among other things, we will see that twin-width behaves well with respect to model theory, is a key concept to handle ordered graphs, and that all the principal width measures can be expressed in terms of contraction sequences. We will propose several open questions.