Given a non-planar graph with a subdivision of as a subgraph, we can either transform the -subdivision into a -subdivision if it is possible, or else we obtain a partition of the vertices of into equivalence classes. As a result, we can reduce a projective planarity or toroidality algorithm to a small constant number of simple planarity checks [6] or to a -subdivision in the graph . It significantly simplifies algorithms presented in [7], [10], and [12]. We then need to consider only the embeddings on the given surface of a -subdivision, which are much less numerous than those of .
