Geodesic
Algorithm and Experiments in Testing Planar Graphs for Isomorphism
Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 313-356.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 provide a proof of the algorithm's correctness and a complexity analysis. 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, Ullmann's, and SUBDUE's (a graph-based data mining system) graph matchers. 
@article{JGAA_2004_8_3_a3,
     author = {Jacek Kukluk and Lawrence Holder and Diane Cook},
     title = {Algorithm and {Experiments} in {Testing} {Planar} {Graphs} for {Isomorphism}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {313--356},
     publisher = {mathdoc},
     volume = {8},
     number = {3},
     year = {2004},
     doi = {10.7155/jgaa.00094},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00094/}
}
TY  - JOUR
AU  - Jacek Kukluk
AU  - Lawrence Holder
AU  - Diane Cook
TI  - Algorithm and Experiments in Testing Planar Graphs for Isomorphism
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 313
EP  - 356
VL  - 8
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00094/
DO  - 10.7155/jgaa.00094
LA  - en
ID  - JGAA_2004_8_3_a3
ER  - 
%0 Journal Article
%A Jacek Kukluk
%A Lawrence Holder
%A Diane Cook
%T Algorithm and Experiments in Testing Planar Graphs for Isomorphism
%J Journal of Graph Algorithms and Applications
%D 2004
%P 313-356
%V 8
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00094/
%R 10.7155/jgaa.00094
%G en
%F JGAA_2004_8_3_a3
Jacek Kukluk; Lawrence Holder; Diane Cook. Algorithm and Experiments in Testing Planar Graphs for Isomorphism. Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 313-356. doi : 10.7155/jgaa.00094. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00094/

Cité par Sources :