### 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*_{5} all of whose extensions to a *K*_{7} have no other non-convex *K*_{5}, 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.

#### Keywords

#### Full Text:

MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.2134.ac9

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications