Geometric thickness of complete graphs

Abstract. We dene the geometric thickness of a graph to be the small-est number of layers such that we can draw the graph in the plane with straight-line edges and assign each edge to a layer so that no two edges on the same layer cross. The geometric thickness lies between two previ-ously studied quantities, the (graph-theoretical) thickness and the book thickness. We investigate the geometric thickness of the family of com-plete graphs, fK n g. We show that the geometric thickness of K n lies between d(n=5:646) + 0:342e and dn=4e, and we give exact values of the geometric thickness of K n for n 12 and n 2 f15; 16g.