Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$

Abstract

There are two properties shared by all known crossing-minimizing geometric drawings of $K_n$, for $n$ a multiple of 3. First, the underlying $n$-point set of these drawings has exactly $3\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)$ $(\le k)$-edges, for all $0\le k<n/3$. Second, all such drawings have the $n$ points divided into three groups of equal size; this last property is captured under the concept of 3-decomposability. In this paper we show that these properties are tightly related: every $n$-point set with exactly $3\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)$ $(\le k)$-edges for all $0\le k<n/3$, is 3-decomposable. As an application, we prove that the rectilinear crossing number of $K_{30}$ is 9726.

14 pages

References in corpus (1)

• New lower bounds for the number of $(\le k)$-edges and the rectilinear crossing number of $K_n$

Cited by in corpus (1)

• Errata and Addenda to Mathematical Constants