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, Passau, Germany , 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
ID Code:216

Repository Staff Only: item control page

References

L. W. Beineke, R. D. Ringeisen, On the crossing number of product of cycles and graphs of order four, J. Graph Theory 4 (1980), 145-155.

M. Hall, Jr., Combinatorial Theory, Blaisdell Publ. Co., Waltham, 1967.

F. Harary, P. C. Kainen, A. Schwenk, Toroidal graphs with arbitrary high crossing numbers, Nanta Mathematica 6 (1973), 58-67.

S. Jendrol', M. Scerbová, On the crossing numbers of S_{m} \times P_{n} and S_{m} \times C_{n}, Casopis pro Pestování Matematiky 107 (1982), 225-230.

P. C. Kainen, A lower bound for crossing number of graphs with applications to K_{n}, K_{p,q} and Q(d), J. Combinatorial Theory, Series B 12 (1972), 287-298.

D. J. Kleitman, The crossing number of K_{5,n}, J. Combinatorial Theory 9 (1970), 315-323.

M. Klesc, On the crossing number of the cartesian product of stars and paths or cycles, Mathematica Slovaca 41 (1991), 113-120.

M. Klesc, The crossing number of product of path and stars with 4-vertex graphs, J. Graph Theory 18 (1994), 605-614.

M. Klesc, On the crossing numbers of products of cycles, preprint.

D. Larman, J. Matousek, J. Pach, J. Töröcsik, A Ramsey-type result for planar convex sets, to appear.

F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983.

F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays. Trees. Hypercubes, Morgan Kaufmann, San Mateo, 1992.

J. Pach, J. Töröcsik, Some geometric applications of Dilworth' theorem, Discrete Computational Geometry, 21(1994), 1-7.

R. B. Richter, I. Stobert, The crossing number of C_{5} \times C_{n}, preprint.

R. B. Richter, C. Thomassen, Intersection of curve systems and the crossing number of C_{5} \times C_{5}, Discrete and Computational Geometry 13 (1995), 149-159.

R. D. Ringeisen, L. W. Beineke, The crossing number of C_{3} \times C_{n}, J. Combinnatorial Theory, Series B 24 (1978), 134-144.

F. Shahrokhi, L. A. Székely, An algebraic approach to the uniform concurrent multicommodity flow problem: theory and applications, Technical Report CRPDC-91-4, Department of Computer Science, University of North Texas, Denton, 1991.

F. Shahrokhi, L. A. Székely, Effective lower bounds for crossing number, bisection width and balanced vertex separators in terms of symmetry, in: Proc. 2-nd IPCO Conference, Pittsburgh, 1992, 102-113, also in Combinatorics, Probability and Computing 3 (1994), 523-543.

F. Shahrokhi, L. A. Székely, I. Vrt'o, Crossing numbers of graphs, lower bound techniques and algorithms: a survey, in: Proc. DIMACS Workshop on Graph Drawing'94, Lecture Notes in Computer Science 894, Springer Verlag, Berlin, 1995, 131-142.

O. Sýkora and I. Vrt'o, On the crossing number of hypercubes and cube connected cycles, BIT 33 (1993), 232-237.

A. T. White, L. W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory, (L. W. Beineke, R. J. Wilson, eds.), Academic Press, N. Y., 1978, 15-50.

K. Wada, K. Kawaguchi, H. Suzuki, Optimal bounds of the crossing number and the bisection width for generalized hypercube graphs, in: Proc. 16th Biennial Symposium on Communications, 1992, 323-326.