Isomorphism identification of graphs: Especially for the graphs of kinematic chains

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. (C) 2008 Elsevier Ltd. All rights reserved.