** 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

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.,

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

December 2003