Projective Planar Graph

A graph with projective plane crossing number equal to 0 may be said to be projective planar. Examples of projective planar graphs with graph crossing number include the complete graph and Petersen graph .

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

For , 2, ..., the first few values are therefore 0, 0, 0, 2, 4, 6, 10, 14, 18, 24, ... (OEIS A128422).