Isomorphism for graphs embeddable on the projective plane
David Lichtenstein · 1980
There are no known polynomial time algorithms for graph isomorphism. For certain classes of graphs, however, efficient algorithms have been found. In particular, there is a polynomial time algorithm for isomorphism of planar graphs [4,5].