Convex drawings of the complete graph: topology meets geometry

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

Abstract


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.


Keywords


Simple drawings, complete graphs, convex drawings

Full Text:

MANUSCRIPT


DOI: 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