Convex drawings of the complete graph: topology meets geometry Article uri icon


  • In a geometric drawing of Kn, 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 Kn in the sphere to be convex if each 3-cycle bounds a closed region R (either of the two sides of the 3-cycle) 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 Kn were convex. However, we take a first step to showing that they are convex: we show that if D has a non-convex K5 all of whose extensions to a K7 have no other non-convex K5, then D is not optimal (without reference to the conjecture for the crossing number of Kn). 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 Kn 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. © 2022 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.

publication date

  • 2022-01-01