Abstract
We provide new tools for the study of branchwidth of graphs, such as $k$-troikas and good subtree-representations, that allow us to give several new results. We show that a graph $G$ has branchwidth at most $k$ if and only if it is a subgraph of a chordal graph in which every maximal clique has a $k$-troika respecting its minimal separators. Moreover, if $G$ itself is chordal with clique tree $T$ then such a chordal supergraph exists having clique tree a minor of $T$. We use these tools to give a straightforward $O(m+n+q^2)$ algorithm computing branchwidth for an interval graph on $m$ edges, $n$ vertices and $q$ maximal cliques. We also prove a conjecture of F. Mazoit \cite{Maz04a} by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees. Finally, we propose a characterization of $k$-branches, namely those graphs of branchwidth $k$ having a maximal set of edges.