Planar branch decompositions. I: The ratcatcher.

*(English)*Zbl 1239.05176Summary: 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 [P.D. Seymour and R. Thomas, “Call routing and the ratcatcher,” Combinatorica 14, No. 2, 217–241 (1994; Zbl 0799.05057)]. 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.

[See also part II of this paper, ibid. 17. No. 4, 413–421 (2005; Zbl 1239.05177).]

[See also part II of this paper, ibid. 17. No. 4, 413–421 (2005; Zbl 1239.05177).]

##### MSC:

05C85 | Graph algorithms (graph-theoretic aspects) |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

68R10 | Graph theory (including graph drawing) in computer science |

68W25 | Approximation algorithms |