2026-09-13T16:03:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22831 2026-09-05T17:57:47Z ddc:004 open_access

Twin-Width One Ahn, Jungho Jacob, Hugo Köhler, Noleen Paul, Christophe Reinald, Amadeus Wiederrecht, Sebastian Twin-width Hereditary graph classes Intersection model 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jungho Ahn and Hugo Jacob and Noleen Köhler and Christophe Paul and Amadeus Reinald and Sebastian Wiederrecht 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.6 urn:nbn:de:0030-drops-228319 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode