Twin-width is a graph and matrix invariant recently introduced by several members of the project in this paper. Many graph classes turn out to have bounded twin-width; for instance, those with bounded treewidth or even bounded rank-width, classes excluding a fixed minor like planar graphs, unit interval graphs, and proper hereditary subclasses of permutation graphs. The structure entailed by having low twin-width allows for a unified treatment of sparse and dense classes —which so far have been dealt with separately—, be it for algorithmic purposes or to derive structural results. Our goal is to elevate twin-width as an indispensable notion in algorithmic graph theory and combinatorics, successfully export it to other fields of mathematics and computer science, and produce an accessible output. The project will run from October 2021 to Fall 2025.
We organized a workshop on twin-width in May 2023. The slides of most talks can be found here.
We organized a workshop on twin-width in May 2023. The slides of most talks can be found here.
