Convex drawings of the complete graph: topology meets geometry
Abstract
In this work, we introduce and develop a theory of convex drawings of the complete graph $K_n$ in the sphere. A drawing $D$ of $K_n$ is convex if, for every 3cycle $T$ of $K_n$, there is a closed disc $\Delta_T$ bounded by $D[T]$ such that, for any two vertices $u,v$ with $D[u]$ and $D[v]$ both in $\Delta_T$, the entire edge $D[uv]$ is also contained in $\Delta_T$. As one application of this perspective, we consider drawings containing a nonconvex $K_5$ that has restrictions on its extensions to drawings of $K_7$. 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\le 12$, every optimal drawing of $K_n$ is convex. Convex drawings are characterized by excluding two of the five drawings of $K_5$. Two refinements of convex drawings are hconvex and fconvex 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 $K_n$, and empty triangles, \rbr{J. Graph Theory DOI: 10.1002/jgt.22167)}, to be equivalent to pseudolinear drawings. Also, hconvex drawings are equivalent to pseudospherical drawings as demonstrated recently by Arroyo et al (Extending drawings of complete graphs into arrangements of pseudocircles, submitted).
 Publication:

arXiv eprints
 Pub Date:
 December 2017
 arXiv:
 arXiv:1712.06380
 Bibcode:
 2017arXiv171206380A
 Keywords:

 Mathematics  Combinatorics;
 05C10;
 05C62;
 68R10