Generating lattice clusters/graphs in parallel

Question

I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What I am looking for is a technique to:

1. Start with a listing of graphs (probably in adjacency matrix format) of size k
2. From this list generate/draw all graphs of size k+1
3. Eliminate those graphs which are disconnected/isomorphic to another graph
4. Keep going until I get graphs with n vertices

Which is either already parallel or reasonably easy to parallelize. I've seen suggestions to use a canonical labelling scheme to cut down on the number of graphs that need to be eliminated through isomorphism at the end. All the graphs I would like to draw are planar and no disconnected graphs are allowed.

[Edit] I'm also wondering whether it would be better to use an adjacency matrix or list to store my graphs - since there will be many hundreds of thousands of them, I'd like a compact storage method.

Answer 1

It turned out my original question was somewhat orthogonal to what I actually needed to do. Since starting with a list (E,V) and mapping it to a particular lattice is "hard", we opted to instead start off with the lattice type assumed. In this case, we specify graphs using coordinates on the lattice, so a 4-cycle on the square lattice would be: (0,0), (0,1), (1,0), (1,1). Using this representation, it's easy to add new sites to a graph (there are four possible positions, check if a site's already there). This also prevents us from generating disconnected graphs. We define two vertices as connected by an edge if they are lattice nearest-neighbours. Since we have several different meanings for "distinct" graphs (depending on the Hamiltonian we are using, it could be distinct under the dihedral group, distinct under x-reflection but not y-reflection, different adjacency lists, etc), we implemented several functions to check for different kinds of isomorphism, depending on which Hamiltonian we are using. We canonise distinct graphs using a simple lexicographic ordering scheme, which allows us to eliminate a huge number of similar graphs. To check if one graph is a subgraph of another, we check if its lattice coordinates can all be shifted by a constant vector so that the resulting list's elements can all be found in the lattice coordinates of the larger graph. Although we haven't implemented any parallelization yet, it seems likely that checking each graph for subgraphs is parallelizable (since a graph with n + 1 vertices can only have graphs of n vertices or below for subgraphs, if all the graphs are non-isomorphic), as is attempting to add sites in all possible positions for a graph and canonising the distinct graphs.