## Crossing Numbers of Meshes
Shahrokhi, Farhad and Sýkora, Ondrej and Székely, László A. and Vrt'o, Imrich
(1996)
Full text not available from this repository. ## AbstractWe 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.
Repository Staff Only: item control page References |