Skip to Main content Skip to Navigation

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
Document type :
Complete list of metadata
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, October 16, 2006 - 9:50:31 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM


  • HAL Id : lirmm-00106678, version 1



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



Record views