Crossing Numbers of Meshes

Shahrokhi, 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 20-22, 1995 , pp. 463-471(Official URL: http://dx.doi.org/10.1007/BFb0021830).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/BFb0021830
Classifications: Z Theory > Z.999 Others
G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/216

Actions (login required)

View Item View Item