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