Crossing Numbers of Meshes

We prove that the crossing number of the cartesian product of 2 cycles, C_{m} \times C_{n}, m \le n, is of order \Omega(mn), improving the best known lower bound. In particular we show that the crossing number of C_{m} \times C_{n} is at least mn/90, and for n = m, m+1 we reduce the constant 90 to 6. This partially answers a 20-years old question of Harary, Kainen and Schwenk [3] who gave the lower bound m and the upper bound (m-2)n and conjectured that the upper bound is the actual value of the crossing number for C_{m} \times C_{n}. Moreover, we extend this result to k \ge 3 cycles and paths, and obtain such lower and upper bounds on the crossing numbers of the corresponding meshes, which differ by a small constant only