On the Crossing Number of Symmetric Configurations

Abstract

For any finite set of points P in general position in the plane, we consider the drawing of the complete graph with vertex set P , whose edges are the straight-line segments joining pairs of points. The crossing number of P is the number of pairs of segments that intersect in their interior. The minimum crossing number over all such sets P of n points is known as the rectilinear or geometric crossing number of the complete graph K_n . The problem of determining this crossing number was posed by Erdős and Guy in the early 1970s and, although it has been extensively studied, it remains open to this date with exact values known only for n ≤ 27 and n = 30. In 2010, it was conjectured that whenever the number of points is a multiple of 3, there are crossing optimal point sets with 3-fold (triangular) rotational symmetry. Motivated by this conjecture, this paper provides lower and upper bounds for sym-crm (Kn ), the rectilinear crossing number of Kn when the minimum is restricted to m-fold symmetric configurations of points in the plane. Our bounds are tight for even symmetry.