The crossing number cr(G) of a graph G is the minimal number of pairwise edge crossings over all drawings of G in the plane. (In a drawing edges may cross one another, but only transversally and only if they are nonadjacent.)

Conjecture: cr(C(n) x C(m)) = n(m-2) where m is at most n.

There exists a drawing with this many crossings. Namely, let the m copies of C(n) be nested regular n-gons with the same center. For each of the n copies of C(m) the vertices lie along a common radii. Complete the C(m) using straight line segments except for a slight curve joining the inside n-gon to the outside one.

The difficulty is in showing that every drawing must have at least this many crossings. Generally the hardest case is n = m, with an induction argument covering n > m.

The conjecture is known to be true for some small values. In particular, it is true for n = 3 [RB], n = 4 [BR], and n = 5 [S].

A generalization exploited by Richter and Thomassen [RT] is to consider graphs $G$ whose edges partition into n+m 2-regular subgraphs (not necessarily connected) A_1,…,A_n,B_1,…,B_m such that each A_i intersects each B_j. It is conjectured that the crossing number of any such graph is at least as large as that of C(n) x C(m).

[BW] L. Beineke and R. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155.

[RB] R. Ringeisen and L. Beineke, The crossing number of C(3) x C(n), J. Combin. Theory B 24 (1978) 134-136.

[RT] R.B. Richter and C. Thomassen, Intersections of curve systems and the crossing number of C(5) x C(5), preprint (1993).

[S] I. Stobert, The crossing number of C(5) x C(n), Honour's Thesis, Carleton University (1993).

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.