Graph Width Measures for CNF-Encodings with Auxiliary Variables

Stefan Mengel, Romain Wallon

We consider bounded width CNF-formulas where the width is measured by popular graph width measures on graphs associated to CNF-formulas. Such restricted graph classes, in particula…