Convex drawings of the complete graph: topology meets geometry
In this work, we introduce and develop a theory of convex drawings of the complete graph Kn in the sphere. A drawing D of Kn is convex if, for every 3-cycle T of Kn, there is a closed disc ΔT bounded by D[T] such that, for any two vertices u,v with D[u] and D[v] both in ΔT, the entire edge D[uv] is also contained in ΔT. As one application of this perspective, we consider drawings containing a non-convex K5 that has restrictions on its extensions to drawings of K7. For each such drawing, we use convexity to produce a new drawing with fewer crossings. This is the first example of local considerations providing sufficient conditions for suboptimality. In particular, we do not compare the number of crossings {with the number of crossings in} any known drawings. This result sheds light on Aichholzer's computer proof (personal communication) showing that, for n≤12, every optimal drawing of Kn is convex. Convex drawings are characterized by excluding two of the five drawings of K5. Two refinements of convex drawings are h-convex and f-convex drawings. The latter have been shown by Aichholzer et al (Deciding monotonicity of good drawings of the complete graph, Proc.~XVI Spanish Meeting on Computational Geometry (EGC 2015), 2015) and, independently, the authors of the current article (Levi's Lemma, pseudolinear drawings of Kn, and empty triangles, \rbr{J. Graph Theory DOI: 10.1002/jgt.22167)}, to be equivalent to pseudolinear drawings. Also, h-convex drawings are equivalent to pseudospherical drawings as demonstrated recently by Arroyo et al (Extending drawings of complete graphs into arrangements of pseudocircles, submitted).
