Small meshes of curves and their role in the analysis of optimal meshes

An (m,n)-mesh is a pair (B,R) of families of closed curves in the plane, of sizes m and n, respectively, such that each curve in B intersects each curve in R. As Richter and Thomassen observed, the minimum number i(*)(m,n) of intersections in an (m,n)-mesh is closely related to the crossing number of the Cartesian product C m×C n. In their work on intersections of curve systems, Shahrokhi et al. proved general lower bounds for i(*)(m,n), and showed that the exact knowledge of i(*)(k,k) yields considerably good bounds for i(*)(m,n) if m,nk, and m is very close to n. Our aim in this paper is to show that comparable (slightly improved) bounds can be obtained by a careful analysis of the nature of the intersections in certain very small (3,k)-meshes. The advantage of this approach is that the analysis of (3,k)-meshes seems to be a far easier task than the exact computation of i(*)(k,k) for large values of k. © 2002 Elsevier Science B.V. All rights reserved.

VIVO