Enumeration of projective-planar embeddings of graphs (Q1087549)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumeration of projective-planar embeddings of graphs |
scientific article |
Statements
Enumeration of projective-planar embeddings of graphs (English)
0 references
1986
0 references
Two embeddings \(f_ 1,f_ 2:\) \(G\to X\) of a graph G into a surface X are said to be equivalent if there exist an automorphism k of G and a self-homeomorphism h of X such that \(h\circ f_ 1=f_ 2\circ k\). In particular, the well-known theorem of H. Whitney states that any two embeddings of a 3-connected graph in the 2-sphere \(S^ 2\) are equivalent. If G is a graph embedded in the projective plane \(P^ 2\) then this embedding can be lifted via the canonical 2-fold covering projection \(p: S^ 2\to P^ 2\) to an embedding of a 2-fold covering graph \(p^{-1}(G)\) into \(S^ 2\). The author observes that, for a non- planar 3-connected graph G, the planar double cover \(p^{-1}(G)\) is also 3-connected. This fact together with Whitney's theorem and some non- trivial results from topology (such as Smith's theory or Brouwer's fixed point theorem) are combined to prove the following results. Theorem 1. There is a bijection between the equivalence classes of embeddings of a 3-connected non-planar graph G into the projective plane and the isomorphism classes of planar double covering graphs over G. Corollary 2. A connected non-planar graph is embeddable into the projective plane if and only if it has a planar double covering.
0 references
equivalent embeddings
0 references
projective plane
0 references
double covering graphs
0 references