Tutte Colloquium - Bruce Richter

Title: Extending drawings of K(n) to pseudolines and pseudocircles

Abstract:

In the early part of the 21st century, it was shown that the number of crossings in a straight-line drawing of K(n) is at least the number H(n), which is conjectured to be the crossing number of K(n). In fact, it is now known that, for n at least 10, the inequality is strict. These methods have been extended to pseudolinear drawings in the plane. Here, each edge extends to an arc going off to infinity in both direction and any two such arcs intersect exactly once, always a crossing. The best result to date is that the 2-page crossing number of K(n) is exactly H(n). However, efforts in this direction have now stalled.

The known drawings of K(n) that have H(n) crossings are all spherical, each edge using the short arc of the great circle containing the two end vertices. Since the generalization from rectilinear to pseudolinear has proved successful in learning more about the straight-line crossing number of K(n), it would be nice to have an analogous generalization to pseudospherical drawings.

We introduced the class of convex drawings of K(n) and their refinements to hereditarily- and face-convex drawings. We have shown that face-convex drawings are exactly the pseudolinear drawings in the plane. We have shown that hereditarily-convex drawings of K(n) are characterized by having a simple closed curve extension C(e) for each edge e such that: the only vertices in C(e) are the ends of e; for distinct edges e,f, C(e) and C(f) have exactly two intersections, both crossings; and, for distinct edges e,f, e crosses C(f) at most once.  

The proof uses interesting characterizations of when a family of simple closed curves has all pairs crossing at most twice. The result also leads to questions about such extensions for graphs other than complete graphs.