Computing Branch Decomposition of Large Planar Graphs

A graph of small branchwidth admits efficient dynamic programming algorithms for many NP-hard problems on the graph. A key step in these algorithms is to find a branch decomposition of small width for the graph. Given a planar graph

G

of

n

vertices, an optimal branch decomposition of

G

can be computed in polynomial time, e.g., by the edge-contraction method in

O

(

n

3

) time. All known algorithms for the planar branch decomposition use Seymour and Thomas procedure which, given an integer

β

, decides whether

G

has the branchwidth at least

β

or not in

O

(

n

2

) time. Recent studies report efficient implementations of Seymour and Thomas procedure that compute the branchwidth of planar graphs of size up to one hundred thousand edges in a practical time and memory space. Using the efficient implementations as a subroutine, it is reported that the edge-contraction method computes an optimal branch decomposition for planar graphs of size up to several thousands edges in a practical time but it is still time consuming for graphs with larger size. In this paper, we propose divide-and-conquer based algorithms of using Seymour and Thomas procedure to compute optimal branch decompositions of planar graphs. Our algorithms have time complexity

O

(

n

3

). Computational studies show that our algorithms are much faster than the edge-contraction algorithms and can compute an optimal branch decomposition of some planar graphs of size up to 50,000 edges in a practical time.