Structure and Linear-Time Recognition of Twin-Width-One Graphs
Graphs of twin-width at most 1 form a well-behaved hereditary class: they are exactly a subclass of permutation graphs (so they carry a permutation-diagram intersection model), their 1-contraction sequences follow the permutation diagram, and a recursive decomposition of their prime induced subgraphs yields a linear-time O(n+m) algorithm that either outputs a 1-contraction sequence or certifies twin-width above 1. The work also characterizes the twin-width of distance-hereditary graphs through their split decomposition.
Twin-width one Jungho Ahn # Ñ
This graph-theory paper determines the structure of graphs of twin-width at most 1 and settles the complexity of recognizing them. Twin-width is a graph width parameter (Bonnet, Kim, Thomasse, Watrig…