TWIN-WIDTH, ANR JCJC project (21-CE48-0014-01)
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.

The team members:

  • Pierre Bergé, (LIMOS, Clermont)
  • Édouard Bonnet, coordinator (LIP, ENS de Lyon)
  • Romain Bourneuf, (master student, LIP, ENS de Lyon)
  • Dibyayan Chakraborty (postdoc, LIP, ENS de Lyon)
  • Hugues Déprés (PhD student, LIP, ENS de Lyon)
  • Julien Duron (PhD student, LIP, ENS de Lyon)
  • Louis Esperet (G-SCOP, Grenoble)
  • Colin Geniet (PhD student, LIP, ENS de Lyon)
  • Ugo Giocanti (PhD student, G-SCOP, Grenoble)
  • Kristóf Huszar (postdoc, LIP, ENS de Lyon)
  • Eunjung Kim (LAMSADE, Paris-Dauphine University)
  • Stéphan Thomassé (LIP, ENS de Lyon)
  • Rémi Watrigant (LIP, ENS de Lyon)