×

zbMATH — the first resource for mathematics

Graphs with branchwidth at most three. (English) Zbl 0946.68103
Summary: We investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognize such graphs. They show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, they give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, output a minimum width branch decomposition.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W10 Parallel algorithms in computer science
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI