Isomorphic Graphs

[dshizzle]

Two graphs are isomorphic, i.e have the same structure, if there exists a function taking one graph to the other which has a bijection between edges, and preserves adjacency and non adjacency of the vertices.

I am considering graphs in a set theoretic sense. A graph is a set of two element sets, where each two element set contains, vertices connected by an edge. I know that I am excluding the case of hyperedges.
Now clearly if two such sets have the same cardinality, there is a bijection between edges. Anybody have an idea how I might determine if there is a function that preserves adjacency and non adjacency?

[dshizzle]

I think that if there exists a function f such that for all vertices of a set A, call them a_n, and all vertices of a set B, call them b_n
1) which is bijective
2) a_1, a_2 element of {a_1,a_2} if and only if b_1, b_2 are an element of {b_1, b_2}

Then the graphs are isomorphic. But this doesn't really give a useful method for determining if two graphs are iso or not. Also sorry for the lack of Tex. I suck I know.

[jestingrabbit]

This is a hard problem.

http://en.wikipedia.org/wiki/Graph_isomorphism_problem

As you can see there, the best that anyone has is an algorithm with complexity O( 2^(n^(1/2) (log^2 n)) ). That's not quick, and it was put together three decades ago.

If you're just trying to work through a couple of examples you can look for easy isomorphism invariants ie the number of vertices that have n edges incident with them, the smallest loop, the largest loop, looking for small graphs that are subgraphs of one but not the other, a vertex of order n adjacent to a vertex of order m etc etc.

[dshizzle]

I see, that is disappointing but not unexpected.

[dshizzle]

What if we restrict ourselves to planar graphs? I would imagine this would drastically cut the time, perhaps to o(n)? I'm going to think on this problem seems more my speed for now.

[Tirian]

That's trickier than you might be suspecting. The duals of two isomorphic planar graphs aren't necessarily isomorphic, so essentially a planar graph can be embedded in a plane in non-trivially different ways.

[dshizzle]

I am new to graph theory, but for a dual D of a graph G, D must have a vertex in every region of G, the same number of edges as G, and each of those edges must connect two regions of G. I don't see how the existence of non-isomorphic duals makes the process more difficult. Care to elaborate?

[letterX]

Googling "planar graph isomorphism" gives this paper as the second result. I didn't read it, but I'm going to go out on a limb here and assume that a paper titled "Planar graph isomorphism is in log-space" actually proves that planar graph isomorphism is in log-space. And hence is in poly-time as well. Doesn't mean it's necessarily O(n), and I rather suspect otherwise.

[dshizzle]

"Planar Graph Isomorphism has been studied in its own right since the early days of
computer science. Weinberg [Wei66] presented an O(n2) algorithm for testing isomorphism
of 3-connected planar graphs. Hopcroft and Tarjan [HT74] extended this to general planar
graphs, improving the time complexity to O(n log n). Hopcroft and Wong [HW74] further
improved it to O(n)." - So it has been reduced to O(n), although clearly not in a trivial manner. Nice paper man.