  The field of knowledge compilation establishes the tractability of many tasks
by studying how to compile them to Boolean circuit classes obeying some
requirements such as structuredness, decomposability, and determinism. However,
in other settings such as intensional query evaluation on databases, we obtain
Boolean circuits that satisfy some width bounds, e.g., they have bounded
treewidth or pathwidth. In this work, we give a systematic picture of many
circuit classes considered in knowledge compilation and show how they can be
systematically connected to width measures, through upper and lower bounds. Our
upper bounds show that bounded-treewidth circuits can be constructively
converted to d-SDNNFs, in time linear in the circuit size and singly
exponential in the treewidth; and that bounded-pathwidth circuits can similarly
be converted to uOBDDs. We show matching lower bounds on the compilation of
monotone DNF or CNF formulas to structured targets, assuming a constant bound
on the arity (size of clauses) and degree (number of occurrences of each
variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of
exponential size in its treewidth, and the same holds for uOBDDs (resp.,
n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds
apply to any formula of this class, not just a well-chosen family. Hence, we
show that pathwidth and treewidth respectively characterize the efficiency of
compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly
exponential in the corresponding width parameter. We also show that our lower
bounds on CNFs extend to unstructured compilation targets, with an exponential
lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of
constant arity and degree to DNNFs (resp., nFBDDs).
