Is there a way to (efficiently) enumerate all simple graphs with a given number of vertices up to isomorphism? That is, I don't care about the degeneracy of a graph, only the set of isomorphically unique ones of a given size.
Enumerating all simple graphs
-
0@Jacob: I like your output. It would be even nicer if you just kept the connected graphs, and tried to present the graphs planarly, if possible, or minimizing intersections! – 2011-01-03
1 Answers
Since almost all graphs have a trivial automorphism group, there are asymptotically $2^{n \choose 2}/n!=O(2^{n^2})$ non-isomorphic graphs.
Suppose you could encode each graph using 1 bit (of course you can't actually do this, but this will help give a lower bound on the complexity). If the input string $n$ is encoded using $O(\log n)$ bits, then merely writing a "1" for each non-isomorphic graph would require at least double-exponential time $O(2^{(2^{\log n})^2})=O(2^{2^{2 \log n}})$.
On top of this, you want to return a string from which you can reconstruct the graph, and (possibly) require some form of isomorphism detection. All in all, this is not going to be easy (no matter how clever your algorithm is).
However, you might want to play around with geng, which comes with nauty, which can generate a list of such graphs. There's probably many other programs as well that I'm not familiar with.