Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2501.00991 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913632853426176 |
|---|---|
| author | Ahn, Jungho Jacob, Hugo Köhler, Noleen Paul, Christophe Reinald, Amadeus Wiederrecht, Sebastian |
| author_facet | Ahn, Jungho Jacob, Hugo Köhler, Noleen Paul, Christophe Reinald, Amadeus Wiederrecht, Sebastian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00991 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Twin-width one Ahn, Jungho Jacob, Hugo Köhler, Noleen Paul, Christophe Reinald, Amadeus Wiederrecht, Sebastian Discrete Mathematics Data Structures and Algorithms Combinatorics 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. |
| title | Twin-width one |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2501.00991 |