We define the geometric thickness of a graph to be the smallest 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 previously studied quantities, the (graph-theoretical) thickness and the book thickness. We investigate the geometric thickness of the family of complete graphs, Kn. We show that the geometric thickness of Kn lies between ceil( (n/5.646) + 0.342 ) and ceil( n/4 ), and we give exact values of the geometric thickness of Kn for n<12 and n in {15,16}.
This is joint work with David Eppstein and Daniel Hirschberg.