  A graphical realization of a linear code C consists of an assignment of the
coordinates of C to the vertices of a graph, along with a specification of
linear state spaces and linear ``local constraint'' codes to be associated with
the edges and vertices, respectively, of the graph. The $\k$-complexity of a
graphical realization is defined to be the largest dimension of any of its
local constraint codes. $\k$-complexity is a reasonable measure of the
computational complexity of a sum-product decoding algorithm specified by a
graphical realization. The main focus of this paper is on the following
problem: given a linear code C and a graph G, how small can the $\k$-complexity
of a realization of C on G be? As useful tools for attacking this problem, we
introduce the Vertex-Cut Bound, and the notion of ``vc-treewidth'' for a graph,
which is closely related to the well-known graph-theoretic notion of treewidth.
Using these tools, we derive tight lower bounds on the $\k$-complexity of any
realization of C on G. Our bounds enable us to conclude that good
error-correcting codes can have low-complexity realizations only on graphs with
large vc-treewidth. Along the way, we also prove the interesting result that
the ratio of the $\k$-complexity of the best conventional trellis realization
of a length-n code C to the $\k$-complexity of the best cycle-free realization
of C grows at most logarithmically with codelength n. Such a logarithmic growth
rate is, in fact, achievable.
