Practical algorithms for branch-decompositions of planar graphs

Branch-decompositions of graphs have important algorithmic applications. A graph G of small branchwidth admits efficient algorithms for many NP-hard problems in G. These algorithms usually run in exponential time in the branchwidth and polynomial time in the size of G. It is critical to compute the branchwidth and a branch-decomposition of small width for a given graph in practical applications of these algorithms. It is known that given a planar graph G and an integer β, whether the branchwidth of G is at most β can be decided in O(n2) time, and an optimal branch-decomposition of G can be computed in O(n3) time. In this paper, we report the practical performance of the algorithms for computing the branchwidth/branch-decomposition of planar G and the heuristics for improving the algorithms.