Crossing Numbers of MeshesShahrokhi, Farhad and Sýkora, Ondrej and Székely, László A. and Vrt'o, Imrich (1996) Crossing Numbers of Meshes. In: Symposium on Graph Drawing, GD 1995, September 2022, 1995 , pp. 463471(Official URL: http://dx.doi.org/10.1007/BFb0021830). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021830
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 20years old question of Harary, Kainen and Schwenk [3] who gave the lower bound m and the upper bound (m2)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.
Actions (login required)
