New Tools and Results for Branchwidth

Christophe Paul 1 Jan Arne Telle
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
keyword : GRAPHS
Type de document :
05017, 2005, pp.14
Liste complète des métadonnées
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 16 octobre 2006 - 09:50:31
Dernière modification le : jeudi 24 mai 2018 - 15:59:22


  • HAL Id : lirmm-00106678, version 1



Christophe Paul, Jan Arne Telle. New Tools and Results for Branchwidth. 05017, 2005, pp.14. 〈lirmm-00106678〉



Consultations de la notice