  Constructions of woven graph codes based on constituent block and
convolutional codes are studied. It is shown that within the random ensemble of
such codes based on $s$-partite, $s$-uniform hypergraphs, where $s$ depends
only on the code rate, there exist codes satisfying the Varshamov-Gilbert (VG)
and the Costello lower bound on the minimum distance and the free distance,
respectively. A connection between regular bipartite graphs and tailbiting
codes is shown. Some examples of woven graph codes are presented. Among them an
example of a rate $R_{\rm wg}=1/3$ woven graph code with $d_{\rm free}=32$
based on Heawood's bipartite graph and containing $n=7$ constituent rate
$R^{c}=2/3$ convolutional codes with overall constraint lengths $\nu^{c}=5$ is
given. An encoding procedure for woven graph codes with complexity proportional
to the number of constituent codes and their overall constraint length
$\nu^{c}$ is presented.
