zbMATH — the first resource for mathematics

Planar branch decompositions. I: The ratcatcher. (English) Zbl 1239.05176
Summary: 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).]

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
Full Text: DOI