  We propose a scheme for generating a weakly chordal graph from a randomly
generated input graph, G = (V, E). We reduce G to a chordal graph H by adding
fill-edges, using the minimum vertex degree heuristic. Since H is necessarily a
weakly chordal graph, we use an algorithm for deleting edges from a weakly
chordal graph that preserves the weak chordality property of H. The edges that
are candidates for deletion are the fill-edges that were inserted into G. In
order to delete a maximal number of fill-edges, we maintain these in a queue. A
fill-edge is removed from the front of the queue, which we then try to delete
from H. If this violates the weak chordality property of H, we reinsert this
edge at the back of the queue. This loop continues till no more fill-edges can
be removed from H. Operationally, we implement this by defining a deletion
round as one in which the edge at the back of the queue is at the front.We stop
when the size of the queue does not change over two successive deletion rounds
and output H.
