The Geometric Thickness of  the Complete Graph




The thickness of a graph G, th(G), is the minimum number of planar graphs whose edge-union is G. Equivalently, partition the edges of G into th(G) sets such that each part gives a planar graph. Usually, the vertices of the graph are allowed to be placed at different points in the plane. The thickness of the complete graph is known [BH], and it is equivalent to the lower bound given by Euler's Theorem. We note that every planar graph has a drawing such that every edge is a straight-line segment.

Consider the following variation. Given a graph G, partition the edges into k planar subgraphs. Each subgraph is to be drawn in the plane such that each edge is a straight-line segment. The additional restriction is that any vertex in two different drawings must be represented by the same point. The minimum number of subgraphs k in any such partition is called the geometric thickness of G, geomth(G). This parameter has also been called the rectilinear thickness of G, as well as the real linear thickness. Such a decomposition is equivalent to a rectilinear embedding of G together with a k-coloring of the edges of G such that no two edges of the same color cross.

The geometric thickness of a general graph G can be much larger than the thickness. In particular, Eppstein [E] has shown that for each k, there is a graph of thickness 3 and geometetric thickness k. He has also examined the outer-planar analogue.

Question: Find the geometric thickness of the complete graph K_n.

The question was apparently first raised by Greenberg in some unpublished work. I read some of his personal notes in the library of the University of Riga in Latvia. He gave a construction that showed geomth(K_n) is at most n/4. I believe the problem was independently introduced by Dillencourt, Eppstein and Hirschberg. They also proved the upper bound, and have proven that the geometric thickness of the complete graph K_n is at least n/5.646.

The website http://www.ics.uci.edu/~eppstein/junkyard/thickness contains further information on this problem. It includes the following:

Question: Find the geometric thickness of the complete graph K_n,m.

The same website gives some results for small values of n and m. The smallest unknown value is K_6,7.

References:

[BH] L.W. Beineke and F. Harary, The thickness of the complete graph, Canad.J. Math 17 (1965) 850-859.

[D] M.B. Dillencourt, D. Eppstein, and D.S. Hirschberg, Geometric thickness of complete graphs, J. Graph Algorithms & Applications, 4(3) (2000) 5-17.

[E]  D. Eppstein, Separating thickness from geometric thickness, preprint.


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu (with thanks to David Eppstein eppstein@ics.uci.edu and to Janis Dambitis)

December 2003