Drawing Rotations in the Plane

Suppose we are given a drawing of the complete graph K_n in the plane (in a drawing nonadjacent edges are allowed to cross at most once transversally). This drawing determines a *local rotation* at each vertex: the (clockwise) cyclic permutation of the edges incident with each vertex from 1 to *n*. This collection of local rotations is called a *rotation*. Rotations are well known to correspond 1-1 with embeddings of K_n in an oriented surface. Less well known is their use in studying drawings in the plane.

For example, there are 16 possible rotations on K_4. Two of these are planar corresponding to the two unique embeddings of K_4 into the oriented plane. Six more correspond to planar drawings of K_4 (there are three ways to choose two nonadjacent crossing edges and two mirror images for each choice). The remaining eight rotations on K_4 cannot be achieved by planar drawings. For example, {0:132,1:023,2:031,3:012} denotes a planar embedding of the complete graph on {0,1,2,3} where *a:bcd* represents the permutation of edges around vertex *a* incident with vertices *(b,c,d)* respectively. Similarly {0:132,1:023,2:031,3:021} represents a permutation which cannot arise in any planar drawing.

**Problem:** *Determine those rotations on* K_n *which can arise from a planar drawing.*

It is tempting to conjecture that a rotation can arise from a planar drawing of *K_n* if and only if the rotation induced on every *K_4* is achievable. However, this is false. The rotation {0:1243,1:2430,2:3041,3:0412,4:1032} on *K_5* cannot be realized by a planar drawing, but every induced *K_4* rotation can be so realized.

This problem arose when trying to find a lower bound for the crossing number of the complete graph (see the related problem ``The Crossing Number of the Complete Graph''). The rotation is sufficient to count the number of crossings in a drawing. Hence a solution to the above problem would reduce finding the minimum crossing number of the complete graph to a purely combinatorial problem.

I note that the problem naturally suggests itself to finding the rotations corresponding to drawings of a arbitrary graph *G*, although without the applications to finding the minimum crossing number of *G*. Another related problem would be to find the minimum genus *g* so that a given rotation *rho* could be realized by a drawing on the sphere with *g* handles---the *crossing genus* of *rho*.

**Problem:** *Find the maximum crossing genus over all rotations on* K_n.

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