Geodesic
Polynomial isomorphism algorithm for graphs which are not contracted to~$K_{3,g}$.
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 99-114

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper describes polynomial-time algorithm which tests isomorphism of undirected graphs uncontracted to Bipartite complete graph $K_{3,g}$. The algorithm may be applied for graphs of bounded valence and for graphs with bounded genus within the same time. Construction of algorithm is based on properties of colour graphs from above class and on results of L. Babai and E. Luks about canonical forms for graphs. 
@article{ZNSL_1984_137_a5,
     author = {I. N. Ponomarenko},
     title = {Polynomial isomorphism algorithm for graphs which are not contracted to~$K_{3,g}$.},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {99--114},
     publisher = {mathdoc},
     volume = {137},
     year = {1984},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a5/}
}
TY  - JOUR
AU  - I. N. Ponomarenko
TI  - Polynomial isomorphism algorithm for graphs which are not contracted to~$K_{3,g}$.
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1984
SP  - 99
EP  - 114
VL  - 137
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a5/
LA  - ru
ID  - ZNSL_1984_137_a5
ER  - 
%0 Journal Article
%A I. N. Ponomarenko
%T Polynomial isomorphism algorithm for graphs which are not contracted to~$K_{3,g}$.
%J Zapiski Nauchnykh Seminarov POMI
%D 1984
%P 99-114
%V 137
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a5/
%G ru
%F ZNSL_1984_137_a5
I. N. Ponomarenko. Polynomial isomorphism algorithm for graphs which are not contracted to~$K_{3,g}$.. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 99-114. http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a5/