A Combinatorial Generalization of Drawing the Complete Graph

A famous problem asks for the minimum number of crossings in any drawing of the complete graph *K_n* in the plane (see "The crossing number of the complete graph"). It conjectures that:

Cr(K_n) = (1/4) [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2]* where ***[m]** *is the integer part of* m*.*

Suppose the vertex set of *K_n* is *I_n = {1,...,n}*. A local neighborhood of a vertex *k* in a planar drawing determines a cyclic permutation of the edges incident with *k* by considering the clockwise ordering in which they occur. Equivalently (looking at the edges' opposite endpoints), it determines a *local rotation* *rho(k)*: a cyclic permutation of *I_n - k*. A (global) *rotation* is a collection of local rotations *rho(k)*, one for each vertex *k* in *I_n*.

It is well known that the rotations of *K_n* are in a bijective correspondence with the embeddings of *K_n* on oriented surfaces. The rotation arising from a planar drawing also determines which edges cross. Namely, edges *ab,cd* cross in the drawing if and only if the induced local rotations on the vertices *{a,b,c,d}* give a nonplanar embedding of that induced *K_4*.

The stated conjecture on the crossing number of *K_n* asserts that the mininum number (over all planar drawings) of induced nonplanar *K_4*'s satisfies the given lower bound. We generalize this to all rotations.

**Conjecture**: *In any rotation of* K_n, *the number of induced nonplanar* K_4*'s is at least* (1/4) [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2]* where *[m]* is the integer part of *m*.*

Not every rotation corresponds to a drawing (see the related problem ``Drawing rotations in the plane''), so this conjecture is strictly stronger than the one on the crossing number of *K_n*. However, this conjecture has the advantage of reducing a geometric problem to a purely combinatorial one.

The problem arose from my attempts to prove the lower bound on the crossing number. It is supported by computer calculations. Namely, I wrote a program which started with a rotation of *K_n* and using a local optimization technique (hill-climbing), randomly swapped edges in a local rotation whenever that swap did not increase the number of induced nonplanar *K(4)*'s. The resulting locally minimal rotations tended to resemble the patterns apparent in an optimal drawing of *K(n)*. For small *n *this minimum was the conjectured upper bound. For larger *n* it was usually slightly larger.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA

Send comments to *dan.archdeacon@uvm.edu*

August, 1995