Computing the branchwidth of interval graphs

Branchwidth is a graph invariant closely related to treewidth, but exhibiting remarkable distinctions. E.g., branchwidth is known to be computable in polynomial time for planar graphs. Our results concern the computational complexity of determining the branchwidth of graphs in several classes. We give an algorithm computing the branchwidth of interval graphs in time O(n3logn). This method generalizes to permutation graphs and, more generally, to trapezoid graphs. In contrast, we show that computing branchwidth is NP-complete for splitgraphs and for bipartite graphs.