Toroidal Crossing Number

The toroidal crossing number of a graph is the minimum number of crossings with which can be drawn on a torus.

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

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