Two graphs G, H. Assume there is an algorithm which can only detect planar graph isomorphism. This means the algorithm gets confused if G and H have different “crossing” which is allowed in “Simple graph”. The algorithm says both G and H are isomorphic to each other when there is no difference between G, H except having different “crossing” which is wrong.

Assume, G and H are isomorphic to each other without considering “crossing” of graphs (though they have different “crossing” which is not considered in the assumption means there is no difference between G, H except having different “crossing” ). For G, make matrix (two dimensional) D_{g}which consists “All-Pair Shortest Path” (APSP) by a polynomial time algorithm (such algorithm exists).Do same for H and get D_{h}. The difference between G and H can be detected in D_{g}, D_{h}. The argument is given below.

For simplicity, assume, both G, H are exactly same except on vertices a, b, c, d. In G, a connected with b, c connected with d. But in H, a connected with c, b connected with d and both pair create two “crossing”. In G, the shortest distance between a, c is more than 1 whereas in H it is exactly 1. These differences are detected in D_{g}, D_{h}.

Set A_{i}= {a, b, c, d} is the set where difference was noticed. Every A_{j}creates a difference in D_{g}, D_{h}.If A is the union of all A_{j}, then total |A| difference exists in D_{g}, D_{h}. If D_{g}, D_{h}are compared(polynomial time), it can be said that G, H are not isomorphic.

A confusion may arise if “APSP Matrix” (e.g. D_{g}, D_{h}) is started from different vertices. This can be solved maintaining some fixed rules and row-column operation simultaneously. APSP can be found by BFS in polynomial time also, I guess.

Procedure:

Two “Simple Graph” G, H are Planar graph-wise isomorphic (i.e. invariants are same except “Crossing”).

1.Get AllPairShortestPath(APSP) matrices of graph G,H ( say g[i][i], h[i][i] respectively).

2. Compare both matrices using a functionF, ifFreturns true, graphs are isomorphic.

The comparing functionFworks as below-

[I]F ( g[i][i] , h[i]){

- [I]Sort elements of g[1][i] , h[1][i], g[i][1], h[I]
[1] in ascending order. // may omit…- //their valency(degree) should be same.
for (j=0; j<i; i++) { /* j row, k column. */for(k=0; k<i; j++) {if(g[j][k]== h[j][k]){K++;}else {e = k;if (D[k]>2)return false; /*each column can’t participate in “interchanging” more than twice */for (l=k+1;l<I; l++){If(g[j][k]== h[j][k]) {Swap e th column and row with l th column and row;D[e]=D[e]+1;l=l+1;} // break} } }} }

** step 1 might be omitted…it was not used in the example.

these are images for example,

Image codes: GI 050914 Page 3

Image codes: GI 050914 Page 4

Image codes: GI 050914 Page 5

Image codes: GI 050914 Page 6