  It is known that any chordal graph on $n$ vertices can be represented as the
intersection of $n$ subtrees in a tree on $n$ nodes. This fact is recently used
in [2] to generate random chordal graphs on $n$ vertices by generating $n$
subtrees of a tree on $n$ nodes. It follows that the space (and thus time)
complexity of such an algorithm is at least the sum of the sizes of the
generated subtrees assuming that a tree is given by a set of nodes. In [2],
this complexity was mistakenly claimed to be linear in the number $m$ of edges
of the generated chordal graph. This error is corrected in [3] where the space
complexity is shown to be $\Omega(m n^{1/4})$. The exact complexity of the
algorithm is left as an open question.
  In this paper, we show that the sum of the sizes of $n$ subtrees in a tree on
$n$ nodes is $\Theta(m\sqrt{n})$. We also show that we can confine ourselves to
contraction-minimal subtree intersection representations since they are
sufficient to generate every chordal graph. Furthermore, the sum of the sizes
of the subtrees in such a representation is at most $2m+n$. We use this result
to derive the first linear time random chordal graph generator. Based on
contraction-minimal representations, we also derive structural properties of
chordal graphs related to their connectivity. In addition to these theoretical
results, we conduct experiments to study the quality of the chordal graphs
generated by our algorithm and compare them to those in the literature. Our
experimental study indicates that the generated graphs do not have a restricted
structure and the sizes of maximal cliques are distributed fairly over the
range. Furthermore, our algorithm is simple to implement and produces graphs
with 10000 vertices and $4 . 10^7$ edges in less than one second on a laptop
computer.
