## Isomorphic Graphs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Isomorphic Graphs

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?
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Isomorphic Graphs

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.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Isomorphic Graphs

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5388
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Isomorphic Graphs

I see, that is disappointing but not unexpected.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Isomorphic Graphs

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.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Isomorphic Graphs

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.
Tirian

Posts: 1557
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Isomorphic Graphs

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?
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Isomorphic Graphs

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.
letterX

Posts: 511
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: Isomorphic Graphs

"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.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman
dshizzle

Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC