On the geometric $k$-colored crossing number of $K_n$

Abstract

We study the \emph{geometric $k$-colored crossing number} of complete graphs ${\overline{\overline{\text{cr}}}}_k(K_n)$, which is the smallest number of monochromatic crossings in any $k$-edge colored straight-line drawing of $K_n$. We substantially improve asymptotic upper bounds on ${\overline{\overline{\text{cr}}}}_k(K_n)$ for $k=2,\dots ,10$ by developing a procedure for general $k$ that derives $k$-edge colored drawings of $K_n$ for arbitrarily large $n$ from initial drawings with a low number of monochromatic crossings. We obtain the latter by heuristic search, employing a \textsc{MAX-$k$-CUT}-formulation of a subproblem in the process.

Extended abstract appearing at Eurocomb'25; 10 pages, 2 figures