Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n1+ϵ) time

We give constant-factor approximation algorithms for computing the optimal branch-decompositions and largest grid minors of planar graphs. For a planar graph G with n vertices, let be the branchwidth of G and the largest integer g such that G has a g×g grid as a minor. Let c≥1 be a fixed integer and α,β arbitrary constants satisfying α>c+1 and β>2c+1. We give an algorithm which constructs in time a branch-decomposition of G with width at most . We also give an algorithm which constructs a g×g grid minor of G with in time. The constants hidden in the Big-O notations are proportional to and , respectively.