Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs

DOI10.1007/978-3-031-15914-5_21arXiv2201.09749OpenAlexW4312510913MaRDI QIDQ6039430

Hugo Jacob, Marcin Pilipczuk

Publication date: 5 May 2023

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.09749

zbMATH Keywords

planar graphstreewidthtwin-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Twin-width can be exponential in treewidth ⋮ Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded

Cites Work

• Rank-width and tree-width of \(H\)-minor-free graphs
• Call routing and the ratcatcher
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• An improved planar graph product structure theorem
• From tree-decompositions to clique-width terms
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Bounds for the Twin-Width of Graphs
• Twin-width I: Tractable FO Model Checking

This page was built for publication: Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs