What is the easiest way to tell if these two graphs are isomorphic and how do I know which nodes in both graphs are the same. I've made the adjacency matrices but they are pretty big. I think I need to find a permutation matrix for the adjacency matrices but that is a lot of work, is there an easier way?
The solution to the problem is:
Best Answer
I was going to say I thought graph isomorphism is NP-complete but lo and behold it's (probably) not. At the very least it is not known to be NP-complete and there are some reason to possibly think it might not be. Even so the most efficient general solutions are not particularly nice.
For a hand worked solution the best thing you can probably do is look for similar "shapes" by which I mean full subgraphs on a few vertices. You can easily see there are some triples of vertices that form triangles and some that don't ($\{d,c,h\}$ does and $\{b,g,f,e\}$ does not) and keep going from there.
Personally I noticed that you get a partition of the set of vertices into two quadruples that form squares $\{a,b,c,d\},\{e,f,g,h\}$ and $\{a^\prime,c^\prime,e^\prime,g^\prime\},\{b^\prime,d^\prime,f^\prime,h^\prime\}$.
I then continued by deforming the graph so that the middle would form a square and the outside would form a square to get a better visual representation attempting to get as close to a planar graph as possible. That meant (going by the original graph 2 intersections). I then used the intersection to get a starting point for constructing my isomorphism. This turns out to be quite straightforward since the graph is tiny and the first try to make it "look right" worked. Though it gave me a different isomorphism $\{a,b,c,d,e,f,g,h\}\to\{f^\prime,d^\prime,b^\prime,h^\prime,e^\prime,g^\prime,c^\prime,a^\prime\}$.