Abstract: The generalized Petersen graph P(n, m) is such a graph that its vertex set is
{u_i, v_i |i=0,1, …, n-1} and edge set is {u_iu_i+1, v_iv_i+m, u_iv_i | i=0,1, …, n-1}, where m, n are positive integers satisfying m< |n/2| and indices is read modulo n. It is proved that the Euler genus of P(2m+1, m)(m≥2) is 1 and that the Euler genus of P(2m+2, m)(m≥5) is 2.

Key words: Cellular embedding, Euler genus, Generalized Petersen graph.