{
  "id": "2307.05811",
  "version": "v1",
  "published": "2023-07-11T21:33:21.000Z",
  "updated": "2023-07-11T21:33:21.000Z",
  "title": "Twin-width of graphs on surfaces",
  "authors": [
    "Daniel Kráľ",
    "Kristýna Pekárková",
    "Kenny Štorgel"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Twin-width is a width parameter introduced by Bonnet, Kim, Thomass\\'e and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin-width of every graph embeddable in a surface of Euler genus $g$ is $18\\sqrt{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\\{8,32g-27\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-11T21:33:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "twin-width",
      "euler genus",
      "single exceptional bag",
      "product structure theorem",
      "quadratic time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}