  A tree decomposition of the coordinates of a code is a mapping from the
coordinate set to the set of vertices of a tree. A tree decomposition can be
extended to a tree realization, i.e., a cycle-free realization of the code on
the underlying tree, by specifying a state space at each edge of the tree, and
a local constraint code at each vertex of the tree. The constraint complexity
of a tree realization is the maximum dimension of any of its local constraint
codes. A measure of the complexity of maximum-likelihood decoding for a code is
its treewidth, which is the least constraint complexity of any of its tree
realizations.
  It is known that among all tree realizations of a code that extends a given
tree decomposition, there exists a unique minimal realization that minimizes
the state space dimension at each vertex of the underlying tree. In this paper,
we give two new constructions of these minimal realizations. As a by-product of
the first construction, a generalization of the state-merging procedure for
trellis realizations, we obtain the fact that the minimal tree realization also
minimizes the local constraint code dimension at each vertex of the underlying
tree. The second construction relies on certain code decomposition techniques
that we develop. We further observe that the treewidth of a code is related to
a measure of graph complexity, also called treewidth. We exploit this
connection to resolve a conjecture of Forney's regarding the gap between the
minimum trellis constraint complexity and the treewidth of a code. We present a
family of codes for which this gap can be arbitrarily large.
