Isomorphism identification of graphs: especially for the graphs of kinematic chains.

*(English)*Zbl 1350.70004Summary: Isomorphism identification of graphs is one of the most important and challenging problems in the fields of mathematics, computer science and mechanisms, etc. This paper attempts to solve the problem by finding a unique representation of graphs. First, the perimeter loop of a graph is identified from all the loops of the graph obtained through a new algorithm. From the perimeter loop a corresponding perimeter graph is derived, which renders the forms of the graph canonical. Then by relabelling the perimeter graph the canonical perimeter graph is obtained, reducing the adjacency matrices of a graph from hundreds of thousands to several or even just one. On the basis of canonical adjacency matrix set, the unique representation of the graph, the characteristic adjacency matrix, is obtained. In such a way, isomorphism identification, sketching, and establishment of the database of common graphs, including the graphs of kinematic chains, all become easy to realize. Computational complexity analysis shows that, in the field of kinematic chains the approach is much more efficient than McKay’s algorithm which is considered the fastest so far. It remains efficient even when the links of kinematic chains increase into the thirties.

##### Keywords:

perimeter graph; kinematic chains; isomorphism identification; characteristic adjacency matrix
PDF
BibTeX
XML
Cite

\textit{H. Ding} and \textit{Z. Huang}, Mech. Mach. Theory 44, No. 1, 122--139 (2009; Zbl 1350.70004)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Luks, E. M.: Isomorphism of graphs of bounded valence can be tested in polynomial time, J. comput. Syst. sci. 25, No. 1, 42-65 (1982) · Zbl 0493.68064 |

[2] | Abdulrahim, M.; Misra, M.: A graph isomorphism algorithm for object recognition, Pattern anal. Appl. 1, No. 3, 189-201 (1998) · Zbl 0911.68182 |

[3] | Messmer, B. T.; Bunke, H.: A decision tree approach to graph and subgraph isomorphism detection, Pattern recogn. 32, No. 12, 1979-1998 (1999) |

[4] | Schmidt, D. C.; Druffel, L. E.: Fast backtracking algorithm to test directed graphs for isomorphism using distance matrices, J. assoc. Comput. Mach 23, No. 3, 433-445 (1976) · Zbl 0357.05049 |

[5] | Ullmann, J. R.: An algorithm for subgraph isomorphism, J. assoc. Comput. Mach 23, No. 1, 31-42 (1976) · Zbl 0323.05138 |

[6] | Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M.: Subgraph transformations for the inexact matching of attributed relational graphs, Comput. suppl. 12, No. 1, 43-52 (1998) · Zbl 0909.68154 |

[7] | L.P. Cordella, P. Foggia, C. Sansone, M. Vento, An improved algorithm for matching large graphs, in: Proceedings of the Third IAPR-TC-15 International Workshop on Graph-based Representations, Italy, 2001, pp. 149 – 159. |

[8] | Mckay, B. D.: Practical graph isomorphism, Congressus numerantium 30, No. 1, 45-87 (1981) · Zbl 0521.05061 |

[9] | Eric, A. B.; Chris, H.: Efficient enumeration and hierarchical classification of planar simple-jointed kinematic chains: application to 12- and 14-bar single degree-of-freedom chains, Mech. Mach theory 40, No. 9, 1030-1050 (2005) · Zbl 1159.70302 |

[10] | Rajesh, P. S.; Linda, C. S.: Structural synthesis of planar kinematic chains by adapting a mckay-type algorithm, Mech. Mach theory 41, No. 9, 1021-1030 (2006) · Zbl 1114.70005 |

[11] | Uicker, J. J.; Raicu, A.: A method for the identification of and recognition of equivalence of kinematic chains, Mech. Mach theory 10, No. 5, 375-383 (1975) |

[12] | Yan, H. S.; Hall, A. S.: Linkage characteristic polynomials: definitions, coefficients by inspection, ASME J. Mech. des. 103, No. 3, 578-584 (1981) |

[13] | Yan, H. S.; Hall, A. S.: Linkage characteristic polynomials: assembly, theorems, uniqueness, ASME J. Mech. des. 104, No. 1, 11-20 (1982) |

[14] | Mruthyunjaya, T. S.: A computerized methodology for structural synthesis of kinematic chains: part 1 – formulation, Mech. Mach theory 19, No. 6, 487-495 (1984) |

[15] | Mruthyunjaya, T. S.: A computerized methodology for structural synthesis of kinematic chains: part 2 – application to several fully or partial known cases, Mech. Mach theory 19, No. 6, 497-505 (1984) |

[16] | Mruthyunjaya, T. S.: A computerized methodology for structural synthesis of kinematic chains: part 3 – application to new case of 10-link, three-freedom chains, Mech. Mach theory 19, No. 6, 507-530 (1984) |

[17] | Mruthyunjaya, T. S.; Balasubramanzan, H. R.: In quest of a reliable and efficient computational test for detection of isomorphism in kinematic chains, Mech. Mach theory 22, No. 2, 131-140 (1987) |

[18] | Sohn, W. J.; Freudenstein, F.: Application of dual graphs to the automatic generation of the kinematic structures of mechanisms, ASME J. Mech. des. 108, 392-398 (1986) |

[19] | A. Ambekar, V. Agrawal, On canonical numbering of kinematic chains and isomorphism problem: max code, in: ASME Mechanisms Conference, 1986. |

[20] | Ambekar, A. G.; Agrawal, V. P.: Canonical numbering of kinematic chains and isomorphism problem: MIN code, Mech. Mach theory 22, No. 5, 453-461 (1987) |

[21] | Tang, C.; Liu, T.: Degree code; a new mechanism identifier, ASME J. Mech. des. 115, No. 3, 627-630 (1993) |

[22] | Shin, J. K.; Krishnamurty, S.: On identification and canonical numbering of pin jointed kinematic chains, ASME J. Mech. des. 116, No. 1, 182-188 (1994) |

[23] | Shin, J. K.; Krishnamurty, S.: Development of a standard code for colored graphs and its application to kinematic chains, ASME J. Mech. des. 114, No. 1, 189-196 (1992) |

[24] | Rao, A. C.; Varada, Raju D.: Application of the Hamming number technique to detect isomorphism among kinematic chains and inversion, Mech. Mach theory 26, No. 1, 55-75 (1991) |

[25] | Rao, A. C.; Rao, C. N.: Loop based pseudo Hamming values – 1. Testing isomorphism and rating kinematic chains, Mech. Mach theory 28, No. 1, 113-127 (1992) |

[26] | Rao, A. C.; Rao, C. N.: Loop based pseudo Hamming values – 2. Inversions, preferred frames and actuator, Mech. Mach theory 28, No. 1, 129-143 (1992) |

[27] | Chu, J. K.; Cao, W. Q.: Identification of isomorphism among kinematic chains and inversions using link’s adjacent chain table, Mech. Mach theory 29, No. 1, 53-58 (1994) |

[28] | Rao, A. C.: Application of fuzzy logic for the study of isomorphism, inversions, symmetry, parallelism and mobility in kinematic chains, Mech. Mach theory 35, No. 8, 1103-1116 (2000) · Zbl 1140.70353 |

[29] | P.R. He, W.J. Zhang, Q. Li, A quadraticform-based approach to identification of kinematic chains in structural analysis and synthesis of mechanisms, in: Proceedings of the 2001 ASME Design Engineering Technical Conferences and Computers and Information Engineering Conference, DETC2001/DAC-21067, Pittsburgh, PA, USA, September 2001, 2001. |

[30] | P.R. He, W.J. Zhang, Q. Li, Eigenvalues and eigenvectors information of graph and their validity in identification of graph isomorphism, in: ASME 2002 Design Engineering Technical Conferences and Computers and Information Engineering Conference, DETC2002/MECH-342147, Montreal, Canada, September 29 – October 2, 2002. |

[31] | He, P. R.; Zhang, W. J.; Li, Q.: A new method for detection of graph isomorphism based on the quadratic form, ASME J. Mech. des. 125, No. 3, 640-642 (2003) |

[32] | He, P. R.; Zhang, W. J.; Li, Q.: Some further development on the eigensystem approach for graph isomorphism detection, Journal of the franklin institute 342, No. 6, 657-673 (2005) · Zbl 1074.05059 |

[33] | Chang, Z. Y.; Zhang, C.; Yang, Y. H.: A new method to mechanism kinematic chain isomorphism identification, Mech. Mach theory 37, No. 4, 411-417 (2002) · Zbl 1140.70322 |

[34] | Cubillo, J. P.; Wan, J. B.: Comments on mechanism kinematic chain isomorphism identification using adjacent matrices, Mech. Mach theory 40, No. 2, 131-139 (2005) · Zbl 1116.70309 |

[35] | Rajesh, P. S.; Linda, C. S.: Reliability and efficiency of the existing spectral methods for isomorphism detection, ASME J. Mech. des. 128, No. 6, 1246-1252 (2006) |

[36] | Rao, A. C.: Genetic algorithm for characteristics of kinematic chains, ASME J. Mech. des. 122, No. 2, 228-231 (2000) |

[37] | Kong, F. G.; Li, Q.; Zhang, W. J.: An artificial neural network approach to mechanism kinematic chain isomorphism identification, Mech. Mach theory 34, No. 2, 271-283 (1999) · Zbl 1049.70545 |

[38] | Mruthyunjaya, T. S.: Kinematic structure of mechanisms revisited, Mech. Mach theory 38, No. 4, 279-320 (2003) · Zbl 1062.70531 |

[39] | Ding, H. F.; Huang, Z.: A unique representation of the kinematic chain and the atlas database, Mech. Mach theory 42, No. 6, 637-651 (2007) · Zbl 1136.70003 |

[40] | Ding, H. F.; Huang, Z.: A new theory for the topological structure analysis of kinematic chains and its applications, Mech. Mach theory 42, No. 10, 1264-1279 (2007) · Zbl 1120.70005 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.