Enumerating all simple graphs

Question

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 isomorphicly isomorphically unique ones of a given size.

Answer 1

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.