Convex drawings of the complete graph: topology meets geometry - Arroyo, Alan (Ars mathematica contemporanea, 2022)
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 ?$\subseteq$? ?$f$?-convex ?$\subseteq$? ?$h$?-convex ?$\subseteq$? convex ?$\subseteq$? 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: complete graphs; convex drawings; enostavne risbe; konveksne risbe; polni grafi; simple drawings