Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
For graph G, let ?bw(G) denote the branchwidth of G and ?gm(G) the largest integer g such that G contains a gg grid as a minor. We show that ?bw(G)?3?gm(G) for every planar graph G. This is an improvement over the bound ?bw(G)?4?gm(G) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3+?)-approximation for the former and (2+?)-approximation for the latter, where ? is an arbitrary positive constant. We also study the tightness of the above bound. We show that for any constant c<2, the bound of \({\mathop {\mathrm {bw}}}(G)\leq c\; {\mathop {\mathrm {gm}}}(G) + o({\mathop {\mathrm {gm}}}(G))\) does not hold in general for a planar graph G.
branchwidth grid graph planar graph graph minor branch-decomposition hypergraph