The 2 and 3 representative projective planar embeddings (Q1186128)

Let \(G\) be a graph embedded on the real projective plane \(P\). The representativity of the embedding is the smallest \(n\) such that there exists a noncontractible curve in \(P\) intersecting \(G\) in \(n\) points. A minor \(H\) of \(G\) is an embedded graph formed by a sequence of either edge delations or edge contractions in \(P\). If \(H\) is a minor of \(G\), then the representativity of \(H\) is at most the representativity of \(G\). So of special interest are the smallest embedded graphs (in the minor ordering) of a given representativity. In this paper the author finds the two minor-minimal embedded projective- planar graphs of representativity at least 2 and the seven minimal embeddings of representativity at least 3. For representativity 2 these are the embedding of the complete graph \(K_ 4\) with every face a quadrilateral and the embedding of the multigraph on 3 vertices with 6 edges each face a triangle. One of the minimal embeddings of representativity 3 is the embedding of \(K_ 6\). The others are related to \(K_ 6\) by a sequence of \(\Delta Y\)-exchanges, deleting the edges of a triangular face while adding a new vertex adjacent to the three vertices of that triangle, or conversely replacing a degree 3 vertex with a triangular face. The projective-planar embedding of the Petersen graph is in this class. The author also examines the minimal projective-planar graphs under the topological order. Here one can delete edges, but can only contract an edge if it is incident with a degree 2 vertex. Every minor-minimal graph of a given representativity is also topologically-minimal. The author shows that there are exactly 2 topologically-minimal embedded graphs of representativity 2 and exactly 15 of representativity 3.