Abstract: We present an algorithm for testing if two graphs are isomorphic and give evidence that its time and space complexity are, on average, linear in the number of nodes and edges in the graphs being compared. The complexities include the cost of matching all the nodes and edges in the two graphs to exhibit the isomorphism, if one exists. We demonstrate results on random graphs, and on non-random graphs with a significant amount of symmetry. Our experiments show that these results hold even when the graphs are sparse, i.e., in cases where the number of edges in the graph is O(N), the number of nodes in the graph. This is a significant extension of other known results where linear complexity is obtained for random graphs only when the node degree increases with N. We present evidence that our algorithm exhibits linear performance not only in the case of random graphs, but also in cases where the randomness is limited; specifically, when the graphs are mesh-like, such as those derived for proteins and other chemical compounds. We present computational experience on graphs with up to 128,000 nodes and 256,000 edges.

Keywords: graph isomorphism, linear complexity algorithm, random graphs and subclasses (mesh, directed, undirected, and sparse).