Drawings of C_m * C_n with One Disjoint Family II

摘要

A long-standing conjecture states that the crossing number of the Cartesian product of cycles C_m * C_n is (m-2) n, for every m,n satisfying n≥m≥3. A crossing is proper if it occurs between edges in different principal cycles. In this paper drawings of C_m * C_n with the principal n-cycles pairwise disjoint or the principal m-cycles pairwise disjoint are analyzed, and it is proved that every such drawing has at least (m-2) n proper crossings. As an application of this result, we prove that the crossing number of C_m * C_n is at least (m-2)n/2, for all integers m,n such that n≥m≥4. This is the best general lower bound known for the crossing number of C_m * C_n.