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(n log(3) n), O(nk(2))} time either constructs a branch-decomposition of G of width at most (2 + delta)k, where delta > 0 is a constant, or a (k+1) x inverted right perpendicular K+1/2 inverted right perpendicular cylinder minor of G implying bw(G) > k, where bw(G) is the branchwidth of G. This is the first (O) over tilde (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min{O(n(1 + epsilon) ), O(nk(2))} (where epsilon > 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 + delta)k and a g x g/2 cylinder/grid minor with g = k/beta where beta > 2 is a constant, can be computed by our algorithm in min{O(n log(3) nlog k), O(nk(2) log k)} time. (C) 2018 Elsevier B.V. All rights reserved.