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