The Geometric Thickness of K13 Is Three: An Exact Integer-Coordinate Witness

Abstract

The geometric thickness of a graph is the minimum number of plane straight-line layers whose union is the graph, with one common placement of the vertices. Dillencourt, Eppstein and Hirschberg left the exact values for K13 and K14 open. We give 13 integer points and a partition of all 78 edges of K13 into three noncrossing layers. Two layers contain at most 2(3·13−6)=66 edges, so the construction proves that the geometric thickness of K13 is exactly three. The certificate is checked by exact segment predicates, by an independent exact-geometry implementation, and by a positive triangulation transported through a threefold affine symmetry.