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

CREATORJungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, Sebastian Wiederrecht
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00991

Browse the full library · About the Tower of Babel