Title: Convex drawings of complete graphs: topology meets geometry
| Speaker: | Bruce Richter |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
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(n2) “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.