Planar graphs on nonplanar surfaces (Q1924159)

It is shown that embeddings of planar graphs in arbitrary surfaces other than the 2-sphere have a special structure. Indirectly, this characterizes graphs on these surfaces whose dual graphs are planar. It turns out that these embeddings can be described in terms of noncontractible curves in the surface, meeting the graph in at most two points (which may be taken to be vertices of the graph). It is proved that such curves pass through all vertices whose local rotation differs from that in a planar embedding of the graph. The close connection between the homology group of the surface and the planar graph embeddings is perhaps the most interesting aspect of this study. Several consequences follow from these results. For example, any two embeddings of a planar graph in the same surface can be obtained from each other by means of simple local re-embeddings very similar to Whitney's switchings. This generalizes Whitney's theorem stating that any two embeddings of a 2-connected graph in the plane can be obtained from each other using a sequence of Whitney's 2-switchings. The structure of embeddings of planar graphs in the projective plane is analysed in more details by \textit{B. Mohar}, \textit{N. Robertson} and \textit{P. R. Vitray} in [Planar graphs on the projective plane, Discrete Math. 149, 141-157 (1996)]. In this paper, such a description is presented for the case of the torus and the Klein bottle under some additional restrictions on the embedding.