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 the graph (Hlinenỳ 2010; Shahmirzadi 2012, p. 7, Fig. 1.1)
is not isomorphic to the graph of Glover and Huneke (1978) and Mohar and Thomassen (2011)
and therefore appears to be incorrectly drawn. Note also 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).
There are exactly 103 projective planar forbidden subgraphs (Glover et al. 1979; Archdeacon 1980, 1981; Mohar and Thomassen
2001).
Archdeacon, D. S. "A Kuratowski Theorem for the Projective Plane." Ph. D. thesis. Columbus, OH: Ohio State University, 1980.Archdeacon,
D. "A Kuratowski Theorem for the Projective Plane." J. Graph Th.5,
243-246, 1981.Glover, H.; and Huneke, J. "The Set of Irreducible
Graphs for the Projective Plane Is Finite." Disc. Math.22<
243-256, 1978.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.Mohar,
B, and Thomassen, C. "The Minimal Forbidden Sugraphs for the Projective Plane."
Appendix A in Graphs
on Surfaces. Baltimore, MD: Johns Hopkins University Press, pp. 247-252,
2001.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.