Monday November 28th at 4.30pm

NP-complete to compute. Unlike the treewidth, this parameter is not up to now that well understood. Many results on branchwidth

only appear very recently. In this talk, we present two new results : 1) a simple and faster algorithm for the branchwidth of interval graphs; and

2) a characterization and algorithmic generation of maximal graph of branchwidth k, called the k-branch.

The latter result can be seen as an analogous work to the k-trees (edge maximal graph of treewidth k) studied by Arnborg and Proskurowski.