Random Generation of Dags for Graph Drawing. Information Systems

摘要

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 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.