Algorithm and Experiments in Testing Planar Graphs for Isomorphism - Kukluk, Jacek; Holder, Lawrence; Cook, Diane (Journal of Graph Algorithms and Applications, 2004)
We give an algorithm for isomorphism testing of planar graphs suitable forpractical implementation. The algorithm is based on the decomposition of agraph into biconnected components and further into SPQR-trees. We provide aproof of the algorithm's correctness and a complexity analysis. We determinethe conditions in which the implemented algorithm outperforms other graphmatchers, which do not impose topological restrictions on graphs. We reportexperiments with our planar graph matcher tested against McKay's, Ullmann's,and SUBDUE's (a graph-based data mining system) graph matchers. <!---->