Random generation of dags for graph drawing

The Graph Drawing community uses test suites for comparing layout quality and efficiency. Those suites often claim to collect randomly generated graphs, although in most cases randomness is a loosely defined notion. We propose a simple algorithm for generating acyclic digraphs with a given number of vertices uniformly at random. Applying standard combinatorial techniques, we describe the overall shape and average edge density of an acyclic digraph. The usefulness of our algorithm resides in the possibility of controlling edge density of the generated graphs. We have used our technique to build a large test suite of acyclic digraphs with various edge density and number of vertices ranging from 10 to 1000.