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

Qian-Ping Gu, Gengchun Xu

We give an algorithm which for an input planar graph $G$ of $n$ vertices and integer $k$, in $\min \{O(n{\log }^{3}n),O(n{k}^2)\}$ time either constructs a branch-decomposition of $G$ with…