Convex drawings of the complete graph: topology meets geometry

Alan Arroyo ; Dan McQuillan ; R. Bruce Richter ; Gelasio Salazar

Ars Mathematica Contemporanea, Tome 22 (2022) no. 3, article no. 04, 27 p.

Résumé

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 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 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.

Détail

DOI : 10.26493/1855-3974.2134.ac9

Keywords: Simple drawings, complete graphs, convex drawings