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:
- Start with a listing of graphs (probably in adjacency matrix format) of size k
- From this list generate/draw all graphs of size k+1
- Eliminate those graphs which are disconnected/isomorphic to another graph
- 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.