Graph isomorphism problem

A generalization of the isomorphism problem is the subgraph isomorphism problem. Given two graphs G1 = (V, ) and... 

The isomorphism problem for general graphs is not an easy one. Given two graphs G- and Gg of n vertices, the number... 

In contrast to the isomorphism problem for general graphs, the isomorphism problem for trees is relatively easy. Any tree with n vertices has exactly n-1 edges. We shall describe an algorithm for constructing, in 0(n) time, a code for any tree, such that two trees are isomorphic if and only if they have... 

A planar graph is a graph which can be drawn on a piece of paper in such a way that no edges cross. Most chemical molecules (with the possible exception of complex organic molecules) are planar (note that this does not mean planar in the sense of stereochemistry). For planar graphs the isomorphism problem also has an easy solution. 

Bangov, I.P. (1992). Toward the Solution of the Isomorphism Problem in Generation of Chemical Graphs Generation of Benzenoid Hydrocarbons. J.Chem.Inf.Comput.Sci.,32,167-173. 

However, a unique enumeration does not solve the problem of substructure search. Superimposition of substructures on structures would require the mapping of any combination of molecular graphs to find a graph isomorphism this is a tedious and time-consuming process. Because the rate of search is always one of the most important limitations for database applications, substructure search should incorporate additional preprocessing steps that restrict the number of molecules to be compared in an atom-by-atom matching algorithm. 

Bangov, l.P. (1992) Toward the solution of the isomorphism problem in generation of chemical graphs generation of benzenoid hydrocarbons. 

Molecular identification numbers (ID) were introduced in 1984 [10] and have been used as molecular descriptors in QSAR [11] although they were constructed initially as a tool for identification of highly similar molecules. We should add that the problem of identification of highly similar molecules is different and distinct from the problem of graph isomorphism in the sense that for the former occasional occurrence of identical ID numbers for distinct structures is acceptable (as it may point to very similar structures), and in the latter, the occurrence of identical numerical values for different structures points to a failure of the approach. In the following section, we give more information on molecular ID numbers and their properties. 

The problem of canonical coding, graph isomorphism, and graph automorphism has both mathematical and chemical significance. The mathematical formulation of the problem is briefly set out below, and some cormections with the chemical counterpart are presented. In the subsequent sections, the main algorithms used in chemistry for canonical coding of molecular graphs and constitutional symmetry perception are presented and compared. 

---