Approximating branchwidth on parametric extensions of planarity
share
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_0 be a graph embeddedable in the projective plane and H_1 be a graph embeddedable in the torus. We prove that every {H_0,H_1}-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_0 and H_1. Moreover, the graph G' admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving an EPTAS for branchwidth: For {H_0,H_1}-minor free graphs, there is a function fℕ→ℕ and a (1+ϵ)-approximation algorithm for branchwidth, running in time 𝒪(n^3+f(1/ϵ)· n), for every ϵ>0.
READ FULL TEXT