Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.