Approximating branchwidth on parametric extensions of 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 $H_1$ be a graph embeddable in the torus and $H_2$ be a graph embeddable in the projective plane. We prove that every $\{H_1,H_2\}$-minor free graph $G$ contains a subgraph $G^{\prime }$ whose branchwidth differs from that of $G$ by a constant depending only on $H_1$ and $H_2$. Moreover, the graph $G^{\prime }$ admits a tree decomposition where all torsos are planar. This decomposition allows for a constant-additive approximation of branchwidth: For $\{H_1,H_2\}$-minor free graphs, there is a constant $c$ (depending on $H_1$ and $H_2$) and an $\mathcal{O}(|V(G){|}^3)$-time algorithm that, given a graph $G$, outputs a value $b$ such that the branchwidth of $G$ is between $b$ and $b+c$.

Accepted to WG 2024

Cited by in corpus (1)

• Revisiting Linear Width: Rethinking the Relationship between Single Ideal and Linear Obstacle