Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs

We give an algorithm that for an input planar graph G of n vertices and an integer k, in min{O(nlog3n),O(nk2)} time either constructs a branch-decomposition of G of width at most (2+δ)k, where δ>0 is a constant, or a (k+1)×k+12 cylinder minor of G implying bw(G)>k, where bw(G) is the branchwidth of G. This is the first Õ(n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n1+ϵ),O(nk2)} (where ϵ>0 is a constant) time constant-factor approximations. For a planar graph G andk=bw(G), a branch-decomposition of width at most (2+δ)k and a g×g2 cylinder/grid minor with g=kβ, where β>2 is a constant, can be computed by our algorithm in min{O(nlog3nlogk),O(nk2logk)} time.