NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question:

Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible.

My attempt at answering this question goes something like this:

• If G1 and G2 have different no. of vertices and/or edges, reject

• Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.

• Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.

At some point, the above algorithm will go thru all n! possible orderings of G1's vertices, and will exhaustively check to see if there's a bijection.

Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1's vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph?

This is all very confusing, and I'm unsure whether I'm thinking thru this problem the right way. I'd appreciate any help.

The algorithm you proposed can be made to work in $O(n \log n)$-space, where $n$ is number of vertices. While permuting the vertices of graph $G_1$, you can also keep the mapping and reverse mapping from and to original vertices. That way you need not rewrite the whole graph. And you can still check if a particular edge in $G_1$ maps to an edge in $G_2$ and vice-versa.

Also, planar graph isomorphism is log-space.

StackExchange Computer Science Q#53766, answer score: 2