Projective Plane Crossing Number

The projective plane crossing number of a graph is the minimum number of crossings with which can be drawn on the real projective plane. Following the convention of putting the surface in the subscript, it is denoted , where denotes the real projective plane. Variants in the literature include , , , and (Schaefer 2026). DeVos et al. (2011) use when organizing crossing numbers for nonorientable surfaces into a crossing sequence. A graph with projective plane crossing number 0 is called a projective planar graph.

In the figure above, the real projective plane is represented by a disk in which each pair of antipodal points on the boundary is identified. A graph edge that reaches the dashed boundary continues from the corresponding antipode, and red points mark crossings. The Petersen graph and Grötzsch graph are shown without crossings and are therefore projective planar graphs. The drawings are crossing-minimal: the projective plane crossing numbers of the Petersen graph, Grötzsch graph, complete graph , and 16-cell graph are 0, 0, 3, and 4, respectively.

For a graph, drawing on the sphere is equivalent to drawing in the plane, but drawing on the real projective plane is not. On the other hand, every drawing in the plane can be placed inside a disk on the real projective plane, so . The additional freedom comes from the cross-cap; in particular, either graph edge at a single crossing in the plane can instead be routed through the cross-cap to remove that crossing.

All graphs with graph crossing number 0 or 1 (i.e., planar and singlecross graphs) have projective plane crossing number 0.

By iterating a result of DeVos et al. (2011, Prop. 1.6), if a disconnected graph , where , is the graph disjoint union of graphs , , and , then

Here denotes the graph crossing number, and the sum ranges over . Thus an optimal drawing can be chosen in which no graph edge of one crosses a graph edge of another . For example, the formula gives , , and .

The projective plane crossing numbers of the complete graphs for , 2, ..., 10 are 0, 0, 0, 0, 0, 0, 3, 9, 18, and 30, respectively (Koman 1969).

Richter and Širáň (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

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