1. Twin-width one
- Author
-
Ahn, Jungho, Jacob, Hugo, Köhler, Noleen, Paul, Christophe, Reinald, Amadeus, and Wiederrecht, Sebastian
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics - Abstract
We investigate the structure of graphs of twin-width at most $1$, and obtain the following results: - Graphs of twin-width at most $1$ are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a $1$-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a $1$-contraction sequence of a graph, or guarantees that it has twin-width more than $1$. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs., Comment: Accepted to STACS 2025
- Published
- 2025