Twin-width one
Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, Sebastian Wiederrecht · 2025
Read Twin-width one by Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, Sebastian Wiederrecht (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00991.txt.
Description
Jungho Ahn and co-authors dissect, in a 2025 paper, the graphs whose twin-width is at most one, the simplest rung of a modern complexity ladder for networks. Twin-width measures how gracefully a graph can be shrunk by merging similar vertices step by step. Graphs at the bottom rung turn out to be tame.
Every such graph, they show, is a permutation graph, with an intersection picture and a linear order behind it. A contraction sequence can always be found that hugs a given permutation diagram. From a recursive splitting theorem they build a linear-time algorithm that either produces the shrinking sequence or certifies the width is higher. Distance-hereditary graphs get a tidy characterization as a bonus, with fast optimal sequences of their own.
Catalog record
| CREATOR | Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, Sebastian Wiederrecht |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00991