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.
Enumerating all simple graphs
-
0In a class I took last spring one of the term projects was on this, his final results are here https://wiki.ucfilespace.uc.edu/groups/combgen/wiki/972b8/Generating_Unlabeled_Graphs.html . – 2010-12-13
-
1This is a difficult problem, which I am sure is exponentially difficult. For low numbers of vertices one can rely on various graph invariants, but in general this is quite complex. I've encountered this issue in calculating bases for "graph homology," but the number of isomorphism classes of graphs blows up quickly. – 2010-12-13
-
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.