I'm interested in all four combinations: directed and undirected, cyclic and acyclic.
I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).
My best guess on a DAG is close to Ω(n!).
[Edit: "multigraphs", obviously, aren't part of the question.]
[Edit2: Looks like for DCGs, it is about 23n. For DAGs, it's about 22n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]