  The constraint complexity of a graphical realization of a linear code is the
maximum dimension of the local constraint codes in the realization. The
treewidth of a linear code is the least constraint complexity of any of its
cycle-free graphical realizations. This notion provides a useful
parametrization of the maximum-likelihood decoding complexity for linear codes.
In this paper, we prove the surprising fact that for maximum distance separable
codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code,
is defined to be the least constraint complexity (or branch complexity) of any
of its trellis realizations. From this, we obtain exact expressions for the
treewidth of these codes, which constitute the only known explicit expressions
for the treewidth of algebraic codes.
