Near-Linear Time Constant-Factor Approximation Algorithm for Branch-Decomposition of Planar Graphs

摘要

We give constant-factor approximation algorithms for branch-decomposition of planar graphs. Our main result is an algorithm which for an input planar graph G of n vertices and integer k, in O(n log~4 n) time either constructs a branch-decomposition of G with width at most (2 + δ)k, δ ＞ 0 is a constant, or a (k + 1) × [k+1/2] cylinder minor of G implying bw(G) ＞ k, bw(G) is the branchwidth of G. This is the first O(n) time constant-factor approximation for branch-width/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n~(1+∈)),O(nk~3)} (∈ ＞ 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw(G), a branch-decomposition of width at most (2+δ)k and a g × g/2 cylinder/grid minor with g = k/β, β ＞ 2 is constant, can be computed by our algorithm in O(n log~4 n log k) time.