Graphs with branchwidth at most three.

*(English)*Zbl 0946.68103Summary: 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.