ICS Theory Group

ICS 269, Fall 1998: Theory Seminar

October 9, 1998:
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, 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.