Graph Isomorphism (Planar Graph).

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 M_{1}. G has total V_{G} vertices. To find G and H are isomorphic,

1. Create matrix N_{G} from M_{1 }which would be filled with vertex degree of G from lowest value to highest (in a row).

2. Create adjacency matrix M_{2 }from M_{1} according to N_{G.}

3. Find the degree which is least in N_{G} (say, degree x was found total t_{x} times in N_{G}).Find it’s corresponding vertices in M_{2}, mark them as ‘w’.

4. Create t_{x} arrays (say, they are g_{1} [], g_{2}[]….g_{t}[]).

5. Run “Breadth-first search” (BFS) in all ‘w’ for V_{G}/t_{x} vertices.

6. While running, for each ‘w’ (parent), array g_{y}[] 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 w_{a }), find the distances from other “w” vertices(using BFS), keep it in array, say in h_{a}[].

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. t_{x}< (V_{G}/2) +1.