Embeddability in the projective plane (i.e., graphs with projective plane crossing number 0) are characterized by a set of exactly 35 forbidden
minors (Glover et al. 1979; Archdeacon 1981; Hlinenỳ 2010; Shahmirzadi
2012, p. 7, Fig. 1.1). Note that this set includes the graph unions and , each member of which is embeddable in the projective plane.
This means that, unlike planar graphs, disjoint unions of graphs which are embeddable
in the projective plane may not themselves be embeddable. As of 2022, the plane and
projective plane are the only surfaces for which a complete list of forbidden minors
is known (Mohar and Škoda 2020).
Richter and Siran (1996) computed the crossing number of the complete bipartite graph on an arbitrary surface. Ho (2005) showed that the projective
plane crossing number of is given by
2, ..., the first few values are therefore 0, 0, 0, 2, 4, 6, 10, 14, 18, 24, ...
Archdeacon, D. "A Kuratowski Theorem for the Projective Plane." J. Graph Th.5, 243-246, 1981.Glover, H.;
Huneke, J. P.; and Wang, C. S. "103 Graphs That Are Irreducible for
the Projective Plane." J. Combin. Th. Ser. B27, 332-370, 1979.Hlinenỳ,
P. "20 Years of Negami's Planar Cover Conjecture." Graphs and Combinatorics26,
525-536, 2010.Ho, P. T. "The Crossing Number of on the Real Projective Plane." Disc. Math.304,
23-33, 2005.Mohar, B. and Škoda, P. "Excluded Minors for
the Klein Bottle I. Low Connectivity Case." 1 Feb 2020. https://arxiv.org/abs/2002.00258.Richter,
R. B. and Širáň, J. "The Crossing Number of in a Surface." J. Graph Th.21, 51-54,
1996.Shahmirzadi, A. S. "Minor-Minimal Non-Projective Planar
Graphs with an Internal 3-Separation." Ph.D. thesis. Atlanta, GA: Georgia Institute
of Technology. Dec. 2012.Sloane, N. J. A. Sequence A128422 in "The On-Line Encyclopedia of Integer