Geometric Thickness of Complete Graphs

Michael Dillencourt, ICS, UC Irvine

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,
K_{n}._{ } We show that the geometric
thickness of K_{n} lies between
ceil( (n/5.646) + 0.342 ) and
ceil( n/4 ), and we give exact values of the geometric
thickness of K_{n} for *n*__<__12 and *
n* in {15,16}.

This is joint work with David Eppstein and Daniel Hirschberg.