Graphs and Matroids Seminar - Bruce Richter

Title: Convex drawings of complete graphs:  topology meets geometry

Abstract:

A drawing D of the complete graph K(n) is the sphere is characterized by, for each isomorph J of K(5), D[J] is homeomorphic to one of the three rectilinear drawings of K(5).  Every drawing of K(n) in the plane with all edges straight-line segments is obviously convex.  Thus, convex drawings generalize planar point sets that are in general position. Some geometric properties of planar point sets carry over to convex drawings:  there are O(n²) “empty triangles” and, for each r, if n is large enough, every convex drawing of K(n) contains a “natural K(r)”. However, our interest is centred on trying to prove that every drawing of K(n) with a minimum number of crossings must be convex.  In this talk, I will describe a theorem that is a first step in this direction.