Approximating Branchwidth on Parametric Extensions of Planarity
摘要
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 investigate an extension of this algorithm to minor-closed graph classes, further than 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'\) where the difference between the branchwidth of G and the branchwidth of \(G'\) is bounded by some constant, depending only on \(H_{1}\) and \(H_{2}\) . Moreover, the graph \(G'\) admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving a constant-additive approximation for 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\) .