Toroidal Crossing Number

The toroidal crossing number of a graph is the minimum number of crossings among its drawings on a torus, and it is 0 iff admits a torus graph embedding.

Every planar graph has toroidal crossing number 0. A nonplanar graph with toroidal crossing number 0 is called a toroidal graph and has graph genus 1, since it can be embedded in a torus but not in the plane.

Neither toroidal crossing number 0 nor projective plane crossing number 0 implies the other, and either crossing number can be arbitrarily large while the other is 0. For projective planar graphs, Gitler et al. (2008, Theorem 1.1) proved that there are positive constants and such that a projective plane graph embedding with face-width implies . Since such graph embeddings can have arbitrarily large face-width, their toroidal crossing numbers are unbounded despite having projective plane crossing number 0.

Conversely, the torus grid graphs have toroidal crossing number 0 but projective plane crossing number for (Riskin 1993). Here, is a cycle graph and denotes the graph Cartesian product.

A graph having graph crossing number or rectilinear crossing number less than 2 has toroidal crossing number 0. More generally, a graph that becomes planar after the removal of a single graph edge (in other words, a graph with graph skewness ) also has toroidal crossing number 0. However, there exist graphs with for which every subgraph obtained by removing a graph edge is nonplanar, so this condition is sufficient but not necessary.

For a graph disjoint union , with and connected, it remains open in general whether a crossing-minimal drawing on the torus can always be chosen with one connected component drawn in a disk (Cabello et al. 2015, Schaefer 2026). Cabello et al. (2015) reduced the problem and proved only a special case. Consequently, no general formula for toroidal crossing numbers of graph disjoint unions analogous to the projective plane or Klein bottle cases is currently known.

If a graph on edges has toroidal crossing number , then (Pach and Tóth 2005), where denotes the binomial coefficient. Furthermore, if is a graph on vertices with maximum vertex degree which has toroidal crossing number , then

(1)

where is a positive constant (Pach and Tóth 2005).

The complete graph has toroidal crossing number 0 for through 7. Guy et al. (1968) proved that the toroidal crossing numbers of , , and are 4, 9, and 23, respectively. For through 16, Guy et al. (1968) exhibited construction upper bound drawings with 42, 70, 105, 154, 226, and 326 crossings, respectively (OEIS A014543), with equality for explicitly stated as a conjecture.

Guy and Jenkyns (1969) obtained the torus case of a formula that Richter and Širáň (1996) generalized to arbitrary surfaces. In particular, for , the toroidal crossing number of the complete bipartite graph is

(2)

where is the floor function. The first values for , 2, ... are therefore 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, ... (OEIS A008724).

Ho (2009) showed that, for , the toroidal crossing numbers of the complete bipartite graph and the complete tripartite graphs and satisfy

(3)

The same value holds for the complete multipartite graphs and . The first values for , 2, ... are therefore 0, 0, 0, 0, 2, 4, 6, 8, 12, 16, 20, 24, 30, 36, ... (OEIS A182568).

The toroidal crossing numbers for a complete bipartite graph are summarized in the following table.

	1	2	3	4	5	6
1	0	0	0	0	0	0
2		0	0	0	0	0
3			0	0	0	0
4				0	2	4
5					5	8
6						12