The Rectilinear Crossing Number of $K_{10}$ is $62$

  • Alex Brodsky
  • Stephane Durocher
  • Ellen Gethner

Abstract

The rectilinear crossing number of a graph $G$ is the minimum number of edge crossings that can occur in any drawing of $G$ in which the edges are straight line segments and no three vertices are collinear. This number has been known for $G=K_n$ if $n \leq 9$. Using a combinatorial argument we show that for $n=10$ the number is 62.

Published
2001-04-09
Article Number
R23