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) Dg which consists “All-Pair Shortest Path” (APSP) by a polynomial time algorithm (such algorithm exists).Do same for H and get Dh. The difference between G and H can be detected in Dg , Dh . 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 Dg , Dh .
Set Ai= {a, b, c, d} is the set where difference was noticed. Every Aj creates a difference in Dg , Dh .If A is the union of all Aj , then total |A| difference exists in Dg , Dh . If Dg , Dh are compared(polynomial time), it can be said that G, H are not isomorphic.
A confusion may arise if “APSP Matrix” (e.g. Dg , Dh ) 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 function F, if F returns true, graphs are isomorphic.
The comparing function F works 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