Planar Branch Decompositions I: The Ratcatcher

The notion of branch decompositions and its related connectivity invariant for graphs, branchwidth, were introduced by Robertson and Seymour in their series of papers that proved Wagner's conjecture. Branch decompositions can be used to solve NP-hard problems modeled on graphs, but finding optimal branch decompositions of graphs is also NP-hard. This is the first of two papers dealing with the relationship of branchwidth and planar graphs. A practical implementation of an algorithm of Seymour and Thomas for only computing the branchwidth (not optimal branch decomposition) of any planar hypergraph is proposed. This implementation is used in a practical implementation of an algorithm of Seymour and Thomas for computing the optimal branch decompositions for planar hypergraphs that is presented in the second paper. Since memory requirements can become an issue with this algorithm, two other variations of the algorithm to handle larger hypergraphs are also presented.