A branch decomposition is a type of graph decomposition closely related to the widely studied tree decompositions introduced by Robertson and Seymour. Unlike tree decompositions, optimal branch decompositions and the branch-width of planar graphs can be computed in polynomial time. The ability to construct optimal branch decompositions in polynomial time leads to efficient solutions for generally hard problems on instances restricted to planar graphs.
This thesis studies efficient algorithms for computing optimal branch decompositions for planar graphs. Our main contribution is an improved software package for graph decompositions with efficient implementations of two additional decomposition classes: carving decompositions and branch decompositions. Polynomial time solutions for Independent-Set on general graphs using path decompositions, tree decompositions, and branch decompositions with bounded width are also explored as examples of how graph decompositions can be used to solve NP-Hard problems.