2026-07-25T22:36:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20622 2024-08-23T05:50:29Z ddc:004 open_access

Twin-Width of Graphs on Surfaces Kráľ, Daniel Pekárková, Kristýna Štorgel, Kenny twin-width graphs on surfaces fixed parameter tractability Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. Hliněný and Jedelský [ICALP'23] showed that every planar graph has twin-width at most 8. We prove that the twin-width of every graph embeddable in a surface of Euler genus g is at most 18√{47g} + O(1), which is asymptotically best possible as it asymptotically differs from the lower bound by a constant multiplicative factor. Our proof also yields a quadratic time algorithm to find a corresponding contraction sequence. To prove the upper bound on twin-width of graphs embeddable in surfaces, we provide a stronger version of the Product Structure Theorem for graphs of Euler genus g that asserts that every such graph is a subgraph of the strong product of a path and a graph with a tree-decomposition with all bags of size at most eight with a single exceptional bag of size max{6, 32g-37}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Kráľ and Kristýna Pekárková and Kenny Štorgel 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.66 urn:nbn:de:0030-drops-206226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.66 eng https://creativecommons.org/licenses/by/4.0/legalcode