Approximating branchwidth on parametric extensions planarity

Abstract

The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated "Ratcatcher" algorithm of Seymour and Thomas. We explore how this algorithm can be extended to minor-closed graph classes beyond planar graphs, as follows: Let H1 be a graph embeddable in the torus and H2 be a graph embeddable in the projective plane. We prove that every {H1, H2}-minor free graph G contains a subgraph G ' whose branchwidth differs from that of G by a constant depending only on H1 and H2. Moreover, the graph G ' admits a tree decomposition where all torsos are planar. This decomposition allows for a constant-additive approximation of branchwidth: For {H1, H2}-minor free graphs, there is a constant c (depending on H1 and H2) and an (| V (G)|3)-time algorithm that, given a graph G, outputs a value b such that the branchwidth of G is between band b + c. (c) 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.