Re-embedding of projective-planar graphs
Seiya Negami · Journal of Combinatorial Theory Series A · 1987
Our graphs are finite, undirected, simple ones combinatorially and have underlying spaces with canonical topology as l-complexes. Let G be a graph and F’ a surface. Two embeddings fi, f2: G -+ F’ are equivalent if there exists a homeomorphism h: F’ + F2 and an automorphism 0: G -+ G such that h 0 fi = f2 3 0. A graph G is said to be uniquely embeddable in F2 if there is precisely one equivalence class of embeddings of G into F’. An automorphism CJ: G + G is called a symmetry of an embeddingf: G -+ F2 if there is a homeomorphism h: F2 + F’ such that h 0 f = f 0 Q. The collection of symmetries off is a subgroup of the automorphism group Aut(G) of G and is denoted by Sym(f ). A graph G is said to be faithfully embeddable in F’ if there is an embeddingf: G + F2 for which Sym( f) = Aut( G). These concepts, the uniqueness and faithfulness of embedding, were defined by the author in [l] where those for toroidal graphs were discussed. The uniqueness of duals of 3-connected planar graphs, proved by Whitney [IS], implies that every 3-connected planar graph is uniquely and faithfully embeddable in a sphere. A graph which is embeddable in a projective plane is called a projectiveplanar graph. Recently, the author has found two large classes of 5-connected projective-planar graphs which are uniquely and faithfully embeddable in a projective plane [2, 31. Actually, he proved the following two theorems: