Optimal branch-decomposition of planar graphs in O ( n 3 ) Time

2008/06/01 by Qian‐Ping Gu, Hisao Tamaki · 89 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Combinatorics #Planar #Decomposition #Planar graph #Mathematics #Graph #Discrete mathematics #Computer science

paper · doi:10.1145/1367064.1367070

published in ACM Transactions on Algorithms 4(3), 1-13 (Association for Computing Machinery)

openalex publication_date 2008/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

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.

Citations

• Constructive linear time algorithms for branchwidth
• Call routing and the ratcatcher
• Graph minors. I. Excluding a forest
• Graph minors. X. Obstructions to tree-decomposition
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k-Tree

Cited by

• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
• Branch-decomposition [wikipedia]