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

M. Cetina, C. Hernández-Vélez, J. Leaños, C. Villalobos

Published 2010-09-23, updated 2011-03-29Version 2

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\binom{k+2}{2}$ $(\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\binom{k+2}{2}$ $(\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.