Convex drawings of the complete graph: topology meets geometry

Abstract

In a geometric drawing of K_n, trivially each 3-cycle bounds a convex region: if two vertices are in that region, then so is the (geometric) edge between them. We define a topological drawing D of K_n to be convex if each 3-cycle bounds a closed region R such that any two vertices in R have the (topological) edge between them contained in R.

While convex drawings generalize geometric drawings, they specialize topological ones. Therefore it might be surprising if all optimal (that is, crossing-minimal) topological drawings of K_n were convex. However, we take a first step to showing that they are convex: we show that if D has a non-convex K₅ all of whose extensions to a K₇ have no other non-convex K₅, then D is not optimal (without reference to the conjecture for the crossing number of K_n). This is the first example of non-trivial local considerations providing sufficient conditions for suboptimality. At our request, Aichholzer has computationally verified that, up to n = 12, every optimal drawing of K_n is convex.

Convexity naturally lends itself to refinements, including hereditarily convex (h-convex) and face convex (f-convex). The hierarchy rectilinear ⊆ f-convex ⊆ h-convex ⊆ convex ⊆ topological provides links between geometric and topological drawings. It is known that f-convex is equivalent to pseudolinear (generalizing rectilinear) and h-convex is equivalent to pseudospherical (generalizing spherical geodesic). We characterize h-convexity by three forbidden (topological) subdrawings.

This hierarchy provides a framework to consider generalizations of other geometric questions for point sets in the plane. We provide two examples of such questions, namely numbers of empty triangles and existence of convex k-gons.