Treewidth d'Incinidence

La largeur d'arbre (treewidth) du graphe d'incidence d'une formule logique ou d'une instance CNF : le graphe d'incidence possède un sommet pour chaque variable et chaque clause, et des arêtes entre une variable et chaque clause qui la contient ; le treewidth d'incidence mesure à quel point cette structure bipartite est proche d'un arbre.