isomorphism for graphs embeddable on the projective plane
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]. This paper presents a generalization of the third theorem to the projective plane, allowing a straightforward adaptation of the planar algorithm to the projective plane. Gary Miller has subsequently generalized my result to surfaces of arbitrary genus, so that there is now a graph isomorphism algorithm which is polynomial for any fixed genus.
graph project polynomial timing algorithm class efficiency planar graph paper general adapt surface