Edge-maximal graphs of branchwidth : The -branches

Abstract: Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most have well-known alternative characterizations as subgraphs of chordal graphs and as partial -trees. In this paper we give analogous alternative characterizations for graphs of branchwidth at most . We first show that they are the subgraphs of chordal graphs where every maximal clique has three subsets of size at most each such that any two subsets have union , with the property that every minimal separator contained in is contained in one of the three subsets. Secondly, we give a characterization of the edge-maximal graphs of branchwidth , that we call -branches. [Copyright &y& Elsevier]