Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
Qian‐Ping Gu, Hisao Tamaki · ACM Transactions on Algorithms · 2008
We give an O ( n 3 ) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in O ( n 4 ) time.