Convex drawings of the complete graph: topology meets geometry
Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

In a geometric drawing of Kn, trivially each 3cycle 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 3cycle bounds a closed region R (either of the two sides of the 3cycle) 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, crossingminimal) 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 nonconvex K5 all of whose extensions to a K7 have no other nonconvex K5, then D is not optimal (without reference to the conjecture for the crossing number of Kn). This is the first example of nontrivial 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 (hconvex) and face convex (fconvex). The hierarchy rectilinear ⊆ fconvex ⊆ hconvex ⊆ convex ⊆ topological provides links between geometric and topological drawings. It is known that fconvex is equivalent to pseudolinear (generalizing rectilinear) and hconvex is equivalent to pseudospherical (generalizing spherical geodesic). We characterize hconvexity 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 kgons. © 2022 Society of Mathematicians, Physicists and Astronomers of Slovenia. All rights reserved.
publication date
funding provided via
published in
Research
keywords

complete graphs; convex drawings; Simple drawings
Identity
Digital Object Identifier (DOI)
PubMed ID
Additional Document Info
start page
end page
volume
issue