Computing the branchwidth of interval graphs Original Research Article

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 image. 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.