Algorithm and experiments in testing planar graphs for isomorphism

We give an algorithm for isomorphism testing of planar graphs suitable for practical implementation. The algorithm is based on the decomposition of a graph into biconnected components and further into SPQR trees. We determine the conditions in which the implemented algorithm outperforms other graph matchers, which do not impose topological restrictions on graphs. We report experiments with our planar graph matcher tested against McKay's, Ullman's, and SUBDUE's (a graph-based data mining system) graph matchers. In general, we are concerned with improving the performance of graph-based data mining systems by taking advantage of fast graph matching for constrained graph topologies.