# Thread: Graph Isomorphism (Planar Graph).

1. Given “Simple” graphs G, H. Total number of vertices, edges and degree of all vertices are same in G and H. The adjacency matrix of graph G is M1. G has total VG vertices. To find G and H are isomorphic,
1. Create matrix NG from M1 which would be filled with vertex degree of G from lowest value to highest (in a row).
2. Create adjacency matrix M2 from M1 according to NG.
3. Find the degree which is least in NG (say, degree x was found total tx times in NG).Find it’s corresponding vertices in M2, mark them as ‘w’.
4. Create tx arrays (say, they are g1 [], g2[]….gt[]).
5. Run “Breadth-first search” (BFS) in all ‘w’ for VG/tx vertices.
6. While running, for each ‘w’ (parent), array gy[] would be filled according to it’s children’s degree of vertex.
7. After finishing each “Level”, fill array with ‘l’.
8. Do step 1 to 7 for graph H.
9. Compare arrays of G and H. If “Bijection” happens, proceed to step 10, otherwise not isomorphic.
10. In G, take any “w” marked vertices(say this is wa ), find the distances from other “w” vertices(using BFS), keep it in array, say in ha[].
up to step 10, works for Planer Graph.

.....(unfinished)
Remarks:
1. Arrays created in step 6, 7 are unique due to step 1, 2.
2. If two ‘w’ are connected with one edge only and this happens z times then z/2 vertices are left out. These vertices are also manageable.
3. tx< (VG/2) +1.

2.

3. Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.

4. Originally Posted by MagiMaster
Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency(Wikipedia), in this case, tx= VG (see remark 3)… I am not Concerned about this. This is probably the only special case and also “manageable” though I have not included it here.Thanks.

5. And I have a marvelous proof of this fact but this forum post is too small to contain it.....

6. Originally Posted by jim198810
Originally Posted by MagiMaster
Two large regular graphs would confuse this algorithm and you'd be left to check all permutations of all vertices in step 9.
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency(Wikipedia), in this case, tx= VG (see remark 3)… I am not Concerned about this. This is probably the only special case and also “manageable” though I have not included it here.Thanks.
Yes... although I wouldn't really call that a special case as any graph that's even half regular (that is, half the vertices have the same degree) will cause your algorithm headaches.

7. @ river_rat , you don't nedd to quote Fermat , it is unnecessary. Of course i don't have rigorous proof.If I had, I would not come to this forum for discussion.But yes, I have some arguments, i am checking it currently. whether I have a proof or not I am going to share my arguments within a few days.Any counterexample would help me and that was the main reason I shared in this forum.

@MagiMaster, yet I am not concerned about regular graph.I gave algo: for simple graph and my main concern was "crossing". I have included steps 10 to 13.Same degree vertices cause problem when they cross in one graph and do not in another.You may check now.

The whole algorithm is quite big and i am writing it part by part.

Thanks both of you!!

8. Just to be clear, for it to be a polynomial time algorithm for graph isomorphism, it needs to handle any and all graphs.

That said, the algorithm there is getting fairly long. An example might help see how it's all supposed to work.

9. Should work , Any counter example???

10. You probably shouldn't edit such old posts. It makes the rest of the thread kind of confusing.

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement