ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P3.04 / 415–441
https://doi.org/10.26493/1855-3974.2134.ac9
(Also available at http://amc-journal.eu)
Convex drawings of the complete graph:
topology meets geometry*
Alan Arroyo †
University of Waterloo, Waterloo, Ontario, Canada,
current address: Vienna, Austria
Dan McQuillan
Norwich University, Northfield, Vermont, United States
R. Bruce Richter ‡
University of Waterloo, Waterloo, Ontario, Canada
Gelasio Salazar §
Universidad Autónoma de San Luis Potosı́, Mexico
Received 1 October 2019, accepted 8 September 2021, published online 24 June 2022
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 in the sphere to be convex if each 3-cycle bounds a closed
region R (either of the two sides of the 3-cycle) 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 draw-
ings 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 suffi-
cient conditions for suboptimality. At our request, Aichholzer has computationally verified
that, up to n = 12, every optimal drawing of Kn is convex.
*We are very grateful to the referees for their detailed reading and useful suggestions for some simplifications
and improving presentation. We also appreciate the contributions of Matthew Sullivan and Kasper Szabo Lyngsie
for simplifying some of our original arguments.
†Supported by CONACYT.
‡Corresponding author. Supported by NSERC grant #50503-10940-500.
§Supported by CONACYT.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
416 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
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.
Math. Subj. Class. (2020): 05C10
1 Introduction
Hill’s long-standing conjecture [14, 10] asserts that the crossing number cr(Kn) of Kn is
equal to
H(n) :=
1
4
⌊
n
2
⌋⌊
n− 1
2
⌋⌊
n− 2
2
⌋⌊
n− 3
2
⌋
.
To date, Hill’s conjecture has only been verified up to n ≤ 12. Moreover, current proofs for
n = 11, 12 rely on extensive computer searches, therefore providing limited explanation for
the elegance of the expression in Hill’s conjecture. Guy’s [13] original proof for n = 9, 10
also relied on an extensive case analysis, with most details left to the reader, similar to a
computer proof.
The main point of this work is the introduction of the class of convex drawings of
Kn. It turns out that, of the (up to spherical homeomorphisms) five drawings of K5 in the
sphere, the drawings K̃35 and K̃55 in Figure 1 are not convex in our sense. Furthermore, an
elementary but principal result of this work is to characterize (rather than define) a spherical
drawing of Kn as convex if and only if neither K̃35 nor K̃55 occurs as a subdrawing.
Our study of these drawings was motivated by a couple of specific events. One was
the computer-free proof by two of the authors that the crossing number of K9 is 36 [21].
As part of that proof, the two drawings K̃35 and K̃55 were both shown not to occur in any
optimal (that is, fewest crossings) drawing of K7. Another was the question, “Is there, for
some n, an optimal drawing (or even one with the conjectured fewest crossings) of Kn that
contains K̃55?”
One of us asked Tilo Wiedera to check by computer if any optimal drawing of K9
contains a K̃55. Not only was the answer negative as expected, but Wiedera also found that
the smallest number of crossings in a drawing of K9 that contains K̃55 has 40 crossings –
a surprising 4 more than optimal! At the Crossing Number Workshop in Osnäbruck (May
2017), the authors then asked Aichholzer for the smallest n for which an optimal drawing
of Kn could contain it. After checking for both K̃35 and K̃55 among all optimal drawings
for Kn with n ≤ 12, he announced at the workshop his findings, implying that if such n
exists, it must be at least 13. Theorem 5.1 below gives further evidence that the answer to
the question is “no”.
E-mail addresses: alanarroyoguevara@gmail.com (Alan Arroyo), dmcquill@norwich.edu (Dan McQuillan),
brichter@uwaterloo.ca (R. Bruce Richter), gsalazar@ifisica.uaslp.mx (Gelasio Salazar)
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 417
Figure 1: Drawings of interest: K̃35, K̃55, K116 , and TC8.
Thus, we were quite naturally led to the class of simple (i.e., no edge crosses itself and
no two closed edges intersect twice; often referred to as “good”) drawings of Kn in which
neither K̃35 nor K̃55 occurs; we first thought of these as “locally rectilinear”, as, of the (up to
spherical homeomorphisms) five drawings of K5 in the sphere, these are the two that are
not isomorphic (via a homeomorphism from the sphere with an appropriate point deleted
to the plane) to rectilinear drawings of K5. We became especially interested in them when
we realized they have a topological characterization (Theorem 2.6, below), which we have
since taken to be the definition of convex drawings in Definition 1.1 below.
If D is a drawing of a graph G, and H is a subgraph of G (or even a set of vertices and
edges of G), then we let D[H] denote the drawing of H induced by D. In a simple drawing
D of a graph G, for a 3-cycle T of G, D[T ] is a simple closed curve.
Definition 1.1. Let D be a simple drawing of Kn in the sphere.
1. If T is a 3-cycle in Kn, then a closed disc ∆ bounded by D[T ] is a convex side of T
if, for any distinct vertices x and y of Kn such that D[x] and D[y] are both contained
in ∆, then D[xy] is also contained in ∆.
2. The drawing D is convex if every 3-cycle of Kn has a convex side.
Evidently every rectilinear or spherical geodesic drawing is convex. Therefore, the “tin
can” drawing TC8 of K8 shown in Figure 1 is convex (see Section 2); it is not homeomor-
phic to any rectilinear drawing. Indeed, K8 is known to have rectilinear crossing number
of 19, while TC8 is optimal with the minimum of 18 crossings.
Wagner [25] showed that establishing the Hill Conjecture for spherical geodesic draw-
ings is equivalent to the special case of the Spherical Generalized Upper Bound Con-
jecture for arrangements of n hemispheres in an (n − 4)-dimensional sphere. In par-
ticular, proving the convex or h-convex crossing number of Kn is H(n) would estab-
lish this case of the SGUBC. Flag algebras are used by Balogh et al. [7] to show that
limn→∞ cr(Kn)/H(n) > 0.985. Restricted to convex drawings, the same technique gets
a lower bound of 0.996. The 0.996 is also the lower bound for spherical geodesic drawings
(these are all necessarily convex).
There are two natural refinements of Definition 1.1; the first is satisfied by spherical
geodesic drawings, while the second holds for rectilinear and pseudolinear drawings.
Definition 1.2. Let D be a convex drawing of Kn.
1. Then D is hereditarily convex (abbreviated to h-convex) if, for every 3-cycle T ,
there is a choice ∆T of a convex side, such that, if T1 and T2 are 3-cycles with
D[T2] ⊆ ∆T1 , then ∆T2 ⊆ ∆T1 .
418 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
2. Then D is face convex (abbreviated to f-convex) if there is a face Γ of D such that,
for every 3-cycle T of Kn, the side of D[T ] disjoint from Γ is convex.
The drawing K116 of K6 shown in Figure 1 is convex but not h-convex. The (optimal)
drawing TC8 of K8 is h-convex but not f-convex.
It is an easy exercise to prove that an f-convex drawing is also h-convex. Moreover, ev-
ery rectilinear (or, more generally, pseudolinear) drawing of Kn is f-convex, with (in both
cases) Γ being the unbounded face. In fact, Aichholzer et al. [4] and, independently, the
current authors [5], have shown that f-convex is equivalent to pseudolinear. Generalizing
spherical geodesic drawings, Arroyo et al. [6] have introduced a natural notion of “pseu-
dospherical drawings” of Kn in the sphere; surprisingly, they are exactly the h-convex
drawings.
It would be very interesting to obtain an analogous “geometric-style” generalization
that characterizes convexity. At this time, we have no suggestion for what this might be.
Thus, our definitions regarding drawings of complete graphs correspond precisely to
geometric descriptions of point-sets. These geometric connections open up new possibil-
ities for studying geometric questions to see how the results differ for convex drawings.
For complete graphs, we now have a geometrically meaningful hierarchy of drawings. It
is, from most to least restrictive: rectilinear ⊆ f-convex (= pseudolinear) ⊆ h-convex (=
pseudospherical) ⊆ convex ⊆ topological.
One question of long-standing interest is: given n points in general position in the plane,
how many of the 3-tuples (that is, triangles) have none of the other points inside the triangle
(empty triangle)? Currently, we know that there can be as few as about 1.6n2+o(n2) empty
triangles [9] and every set of n points has at least n2+O(n) empty triangles (n2+o(n2) first
proved in [8]). In [5], we proved the n2 + o(n2) bound also holds for f-convex drawings.
At the other extreme, Harborth [15] presented an example of a topological drawing of Kn
having only 2n−4 empty triangles, while Aichholzer et al. [3] show that every topological
drawing of Kn has at least n empty triangles. We have shown in [5] that every convex
drawing of Kn has at least 13n
2 + O(n) empty triangles. For h-convex, it is shown in [6],
using the f-convex result and other facts about h-convex drawings, that there are at least
3
4n
2+o(n2) empty triangles. We would be interested in progress related to the coefficients
1
3 and
3
4 .
Another question of interest is: given n points in general position in the plane, what
is the largest k so that k of the n points are the corners of a k-gon in convex position? In
Theorem 3.4, we generalize to convex drawings the Erdős-Szekeres theorem [12] that, for
every k, there is an n such that every set of n points in the plane in general position has a
set of k points that are the corners of a convex k-gon. Finding the least such n is of current
interest. Suk [24] has shown that 2k+o(k) points suffices in the geometric case. For k = 5,
9 points is best possible in the rectilinear case (see Bonnice [11] for a short proof).
For a general drawing D of Kn, we can ask whether there is a subdrawing D[Kk] such
that one face is bounded by a k-cycle: this is a natural drawing of Kk. (In [21], these
drawings are quite appropriately labelled “convex”. We think convex is very descriptive of
the drawings considered in this work and expect there to be no confusion with the two quite
different uses of the term “convex”.) Bonnice’s proof adapts easily to the pseudolinear case
(that is, the f-convex case). Aichholzer (personal communication) has verified by computer
that 11 points is best possible for k = 5 for the convex drawings considered in this article.
A trivial consequence of our Theorem 4.5 characterizing h-convex drawings is that any
convex, but not h-convex, drawing has a natural K5; therefore, 11 is also best possible
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 419
for h-convex drawings. For general drawings of Kn, there need not be a natural K5. In
Harborth’s example [15] (originally from [16]), every K5 is isomorphic to K̃55.
We remark that Pach et al. [23] show that, for any fixed positive integer r, there is
a large enough integer N = N(r) such that, for n ≥ N , every simple drawing of Kn
contains either a natural Kr or Harborth’s generalization of K̃55 on r vertices. In Harborth’s
generalization, every K5 is isomorphic to K̃55. These are the “twisted” Krs in [23].
Section 2 introduces many fundamental properties of a convex drawing D of Kn, in-
cluding showing convexity of D is equivalent to not containing either of the two non-
rectilinear drawings K̃35 and K̃55 of K5 (the first two drawings in Figure 1). Another equiv-
alence is that every 3-cycle T has a side such that every vertex v on that side is such that
D[T + v] is a non-crossing K4.
Section 3 proves that a convex drawing D of Kn has a particularly nice structure: there
is a natural Kr such that D[Kr] has a face Γ bounded by an r-cycle C; if D[v] is in Γ and
D[w] is in the closure of Γ, then D[vw] is in Γ ∪ {D[w]}; and if D[v] and D[w] are in
the closure of the complement of Γ, then D[vw] is in the complement of Γ. This structure
theorem may provide a strategy for showing that a convex drawing of Kn has at least H(n)
crossings.
Section 4 treats h-convex drawings. The main result here is that a convex drawing D
is h-convex if and only if there is no K6 such that D[K6] is K116 in Figure 1. We do not
know a comparable result distinguishing f-convex drawings from h-convex. The tin can
drawing TC8 of K8 in Figure 1 is one such (as are the larger tin can drawings). However it
is not clear to us whether TC8 is the only minimal one or, indeed, if there are only finitely
many minimal distinguishing examples. The final result of the section is that testing a set
of convex sides for h-convexity is also a “Four Point Property”, which is to say that it can
be verified by checking all sets of four points.
Finally, in Section 5, we prove the principal result Theorem 5.1, showing that some
non-convex drawings of Kn are not optimal.
Table 1: The convexity hierarchy.
level characterization distinguish
general edges share ≤ 1 point
convex general, no K̃35, K̃55 K̃35
h-convex convex, no K116 K116
f-convex h-convex + ?? TC8
rectilinear unlikely Pappus
This work will provide characterizations of the different kinds of convexity and distin-
guishing between them by examples and theorems. A summary is given in Table 1.
Matoušek [19] gives a nice exposition of the theorem of Mnëv [22] that testing the
stretchability of an arrangement of pseudolines in the plane is ∃R-complete. A straightfor-
420 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
ward application of Levi’s Enlargement Lemma [18] (see also [5]) turns such an arrange-
ment with n pseudolines into a pseudolinear drawing of K2n that is not stretchable. Hence,
unless P=NP=∃R, there are infinitely many non-stretchable f-convex drawings of Kn.
2 Convex drawings
In this section we introduce the basics of convexity. We already mentioned in the intro-
duction that the two drawings K̃35 and K̃55 of K5 in Figure 1 are not convex. In fact, their
absence characterizes convexity. We first prove some intermediate results that make this
completely clear. Our first observation is immediate from the definition of convex side and
is surprisingly useful.
Observation 2.1. If J is such that D[J ] is a crossing K4, and T is a 3-cycle in J , then the
side of D[T ] containing the fourth vertex in J is not convex. 2
We had some difficulty deciding on the right definition of convexity. At the level of
individual 3-cycles, the definition given in the introduction makes more sense. At the level
of a drawing being convex, there is a simpler one, as shown in the next lemma and, more
particularly, its Corollary 2.4: we only need to test single points in the closed disc ∆ and
how they connect to the three corners.
Definition 2.2. Let D be a drawing of Kn, let T be a 3-cycle in Kn, and let ∆ be a closed
disc bounded by D[T ]. Then ∆ has the Four Point Property if, for every vertex v of Kn
not in T such that D[v] ∈ ∆, D[T + v] is a non-crossing K4.
Lemma 2.3. Let D be a drawing of K5 such that the side ∆ of a 3-cycle T has the Four
Point Property. Suppose u and v are vertices of K5 such that D[u], D[v] ∈ ∆. If D[uv] is
not contained in ∆, then there is a vertex b of T such that neither side of the 3-cycle induced
by u, v, and b satisfies the Four Point Property; in particular, neither side is convex.
Proof. Since ∆T has the Four Point Property, neither u nor v is in T . Because D[u] and
D[v] are both on the same side of D[T ], D[uv] crosses D[T ] an even number of times.
However, D[uv] crosses each of the three sides of D[T ] at most once, so D[uv] crosses
D[T ] at most three times. Thus, D[uv] crosses D[T ] either 0 or 2 times.
As D[uv] is not contained in ∆T , D[uv] crosses D[T ] a positive number of times. We
conclude they cross exactly twice. Label the vertices of T as a, b, and c so that D[uv]
crosses both D[ab] and D[ac].
Since D[T +u] is a non-crossing K4, the three edges of T +u incident with u partition
∆T into three faces, each incident with a different two of a, b, and c. Because D[uv]
crosses D[ab] and D[ac], but not any of the three edges of T + u incident with u, v must
be in one of the faces of D[T + u] incident with a. We choose the labelling so that v is in
the face of D[T + u] incident with both a and c.
The Four Point Property implies D[vb] is contained in ∆T . It must cross either D[ua]
or D[uc]. To show that it crosses D[uc], we assume by way of contradiction that it crosses
D[ua]. Let × be the point where D[ab] crosses D[uv]. Then D[vb] must exit the region
incident with a, u, and ×, but it cannot cross either D[ab] or D[uv], and it cannot cross
D[au] a second time. This contradiction shows D[vb] crosses D[uc].
Therefore D[T + {u, v}] is isomorphic to K̃35, with u and v being the upper left and
upper right vertices, respectively, and a the peak in Figure 1. Letting b and c be the lower
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 421
left and lower right vertices, respectively, the 3-cycles uvb and uvc have no convex side.
Obviously, if ∆ is a convex side of D[T ], then ∆ has the Four Point Property. The
following converse is an immediate consequence of Lemma 2.3.
Corollary 2.4. Let D be a drawing of Kn and, for each 3-cycle T in Kn, let ∆T be a
closed disc bounded by D[T ]. Suppose, for each T , ∆T has the Four Point Property. Then
each ∆T is convex; in particular, D is convex.
Our next two corollaries yield additional characterizations of convexity.
Corollary 2.5. Let D be a drawing of Kn.
(a) Then D is not convex if and only if there exists a 3-cycle T of Kn and vertices u, w of
Kn, one in the interior of each side of D[T ], such that both D[T + u] and D[T +w]
are crossing K4’s.
(b) If D is convex and T is a 3-cycle in Kn, then a side ∆ of D[T ] is convex if and only
if it satisfies the Four Point Property.
Proof. For Item (a), Observation 2.1 shows that if D is convex, then no such 3-cycle can
exist. Conversely, Corollary 2.4 implies that some 3-cycle T of Kn does not have a side
that satisfies the Four Point Property. This implies that, for each side ∆ of D[T ], there is a
vertex v∆ such that D[T + v∆] is a crossing K4, as required.
The proof of Item (b) is direct from the definition of convex side and Lemma 2.3.
We came to the concept of convexity by considering drawings of Kn without the two
drawings K̃35 and K̃55 (see Figure 1) of K5 for reasons that have been subsumed by some of
the developments described in this article. Since the remaining drawings of K5 are rectilin-
ear, we think of such drawings of Kn as locally rectilinear. Our next result is the surprising
equivalence with convexity and this led us to consider convexity and its strengthenings to
h- and f-convex.
Theorem 2.6. A drawing D of Kn is convex if and only if, for every subgraph J of Kn
isomorphic to K5, D[J ] is not isomorphic to either K̃35 or K̃55.
Proof. In the drawing of K̃35 in Figure 1, we see that a 3-cycle consisting of one of the
edges that is not a straight segment together with the longer horizontal edge has no convex
side. In the drawing of K̃55, there are two 3-cycles that have the “interior vertex” in their
interiors. Neither of these 3-cycles is convex. Thus, these two drawings of K5 cannot occur
in a convex drawing of Kn.
Conversely, in a rectilinear drawing of K5, the bounded side of each 3-cycle has the
Four Point Property. Thus, Corollary 2.4 shows a rectilinear drawing of K5 is convex.
On the other hand, Corollary 2.5 shows every non-convex drawing of Kn contains a non-
convex drawing of K5. Such a drawing is either K̃35 or K̃55.
Theorem 2.6 has the following simple corollary. (To help with phrasing, we refer to an
isomorph J of Kr to mean J is a specific one of the complete subgraphs of Kn having r
vertices.)
422 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
Corollary 2.7. Let D be a drawing of Kn. Suppose, for every isomorph J of K5, there
is, for some m ≤ 12, an isomorph L of Km containing J such that D[L] is an optimal
drawing of Km. Then D is convex.
Proof. Aichholzer [2] has verified that D[L] is convex, so D[J ] is a convex K5.
As illustration of the utility of Corollary 2.7, Ábrego et al. [1] exhibit, for odd n, a
drawing Nn,n,1 of K2n+1 having H(2n + 1) crossings, with every edge involved in at
least one crossing. We argue here that it is convex; furthermore, we believe that analogous
arguments apply to any of the known examples of drawings of Kn having H(n) crossings.
We start with the tin can drawing TC2n of K2n (TC8 is illustrated in Figure 1; in
this figure, the labelling described below is counterclockwise). This has concentric regular
n-gons, the outside one labelled u0, . . . , un−1 and the inside one labelled v0, . . . , vn−1.
For each i, ui and vi are roughly “antipodal”, so ui is closest to vi+⌊n/2⌋. We use the
non-self-crossing perfect matching consisting of the edges uivi+⌊n/2⌋ to work from (the
indices are always read modulo n). We join ui to vi+⌊n/2⌋+1, vi+⌊n/2⌋+2, . . . , vi−1 in one
direction from uivi+⌊n/2⌋ around the cylinder, and to vi+⌊n/2⌋−1, vi+⌊n/2⌋−2, . . . , vi+1, vi
in the other direction. The two sides are as equal as possible. Thus, the rotation at ui is
ui+1, ui+2, . . . , ui−1, vi, vi+1, . . . vi−1 .
We mentioned in the introduction that this is homeomorphic to a spherical drawing and
therefore convex. However, an earlier referee requested more detail for proofs of convexity,
so we provide the argument for TC2n and adapt it to prove the convexity of Nn,n,1.
To argue that TC2n is convex, let V be any set of five vertices in TC2n. These vertices
are covered by at most five edges of the matching M consisting of the antipodal edges uivi.
Add one or two more edges from M as needed to get up to five edges, and use the induced
drawing on these 10 vertices. This is TC10 because the induced rotations of the edges at
the 10 vertices satisfy the rotation described in the preceding paragraph. This is an optimal
drawing of K10, so Corollary 2.7 shows TC2n is convex.
To get the Ábrego et al. drawing Nn,n,1, add a vertex w to TC2n near the centre of the
concentric n-gons. This is joined to the 2n vertices by straight line segments, creating the
drawing TC+2n. The drawing Nn,n,1 is completed by redrawing the edges uivi of TC
+
2n as
illustrated in Figure 2; these are the green edges in their Figure 4. Their labelling and ours
coincide except that our indices on ui and vi are one less than theirs.
v0
v1
v2
v3
u0u1
u2 u3
w
Figure 2: N4,4,1.
Many of the K5’s in Nn,n,1 are exactly the same in TC+2n; all of these are convex.
This is even true for a K5 that contains just one green edge, say u0v0 and no vertex from
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 423
u1, u2, . . . , u⌊n/2⌋: the drawings of this K5 in Nn,n,1 and TC
+
2n are isomorphic. This is
helpful in dealing with the case there is only one green edge: we may assume such a K5
also has at least one of the uj listed in the preceding paragraph.
In case of a single green edge and the green edge is not involved in a crossing, we make
use of the following simple observation.
Observation 2.8. Let D be a convex drawing of K5 and let D′ be another (simple) drawing
of K5 obtained from D by rerouting a single edge e. If e is uncrossed in D′, then D′ is
convex.
Proof. If e is uncrossed in D, then D and D′ are homeomorphic drawings and the result is
trivial. Otherwise, the edge e is crossed in D, so cr(D′) < cr(D). These numbers are both
odd (Kleitman [17]) and at most 5. Since the spherical drawing of K5 with one crossing is
convex, the only non-trivial case is D is the natural drawing of K5.
In this case, e is one of the crossed edges; these are all the same. Only the face of G−e
bounded by the 5-cycle is incident with both ends of e. Thus, D′ is a homeomorph of the
rectilinear drawing whose outer face is bounded by a 4-cycle.
Next, consider a K5 having a unique green edge crossed in the K5. With 4 vertices de-
termined, if the fifth vertex is w or vj , then the K5 is optimal and hence convex. Otherwise,
there are four “u vertices” and it is easy to see that it is one of the rectilinear K5’s.
Lastly, there may be two green edges. Except for one exceptional case when n is even,
these edges must cross. Moreover, they give us four of the vertices of the K5 and it is not
difficult to check the different possible locations for the remaining vertex.
The following definition and corollary to Lemma 2.3 will be used in the next section
for the structural description of a convex drawing.
Definition 2.9. Let D be a drawing of Kn, let u be a vertex of Kn, and let J be a complete
subgraph of Kn − u. If D[J ] is natural and D[u] is in the face of D[J ] bounded by a
|V (J)|-cycle, then u is planarly joined to J if no edge from D[u] to D[J ] crosses any edge
of J .
Corollary 2.10. Let D be a convex drawing of K5 with vertices u, v such that D − {u, v}
is the 3-cycle T . If D[u] and D[v] are in the same face of D[T ] and u and v are both
planarly joined to T , then D[uv] is in the same face of D[T ] as D[u] and D[v].
A further perusal of the five drawings of K5 shows that the following further refinement
of forbidden substructures is possible. This configuration was mentioned at Crossing Num-
ber Workshop 2015 (Rio de Janeiro) in the context of being one forbidden configuration
for a drawing of an arbitrary graph to be pseudolinear. The proof is quite straightforward.
Lemma 2.11. Let D be a drawing of Kn. Then D is convex if and only if, for every path
P of length 4, D[P ] is not isomorphic to P̃4.
We will use the following observation in Section 5. Its proof, left to the reader, is a
good exercise in using the fact that no two closed edges can have two points in common.
Observation 2.12. Let D be a drawing of K5 in which some 3-cycle is crossed three times
by a single edge. Then D is K̃55 (as in Figure 1).
424 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
Figure 3: The drawing P̃4.
3 Convexity and natural drawings of Kn
We recall from Section 1 that a natural drawing of Kn is a drawing in which an n-cycle
bounds a face Γ. It is easy to see that, in any natural drawing of Kn, every 3-cycle T has a
side ∆T that is disjoint from Γ and there is no vertex of Kn in the interior of ∆T . Thus, Γ
and the ∆T show that a natural drawing of Kn is f-convex.
In this section, we show that if D is a convex drawing of Kn with the maximum number(
n
4
)
of crossings, then D is a natural drawing of Kn. This leads us to a structure theorem
for convex drawings of Kn whose central piece is, for some r ≥ 4, a natural drawing of
Kr. It also leads to the Erdős-Szekeres Theorem for convex drawings: for every r ≥ 5, if
n is sufficiently large, then every convex drawing of Kn contains a natural Kr.
Lemma 3.1. Let D be a drawing of Kn. Then D is a convex drawing of Kn with
(
n
4
)
crossings if and only if D is a natural drawing of Kn.
Proof. One direction is trivial; for the other, let D be a convex drawing of Kn with
(
n
4
)
crossings; all K4’s are crossing in D. We proceed by induction on n, the cases n ≤ 5 being
trivial. Let v0 be any vertex of Kn and let H be the Hamilton cycle of Kn − v0 such that
D[H] bounds a face F of D[Kn − v0].
Claim 3.2. If T is a 3-cycle in Kn, then one side of D[T ] has no vertex drawn in its interior.
Proof. Otherwise, the convex side ∆ of D[T ] has a vertex v with D[v] in the interior of ∆.
This yields the contradiction that D[T + v] is a non-crossing K4.
In particular, Claim 3.2 applied to all the 3-cycles in Kn − v0 shows v0 is in F .
Claim 3.3. Suppose x, y, z are distinct vertices of Kn − v0 such that yz ∈ E(H) and the
edge D[v0x] crosses the edge D[yz]. Then, for any vertex w of Kn − {v0, y, z}:
(a) D[v0w] crosses D[yz]; and
(b) yz is the only edge of H crossed by v0w.
Proof. For (a), if D[v0w] does not cross D[yz], then the 3-cycle D[v0wx] has D[y] and
D[z] on different sides, contradicting Claim 3.2.
For (b), in traversing v0w, let ab be the first edge of Kn − v0 such that D[v0w] crosses
D[ab]. Then ab is in H and v0w does not cross either aw or bw. That is, the portion of
D[v0w] from the crossing with D[ab] to D[w] is contained inside the 3-cycle D[abw].
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 425
Since every K4 is crossing, v0 is not planarly joined to D − v0. Therefore, there is
an edge v0x that crosses an edge yz of H . Claim 3.3(a) shows that, for any vertex w of
D − {v0, y, z}, v0w also crosses yz.
If v0y crosses some edge y′z′ of H , then Claim 3.3(a) shows that, for any vertex w
of D − {v0, y′, z′} also crosses y′z′. Note that y /∈ {y′, z′}. Since n ≥ 6, there is a
w0 different from all of v0, y, z, y′, z′, so v0w0 crosses both yz and y′z′, contradicting
Claim 3.3(b).
Replacing the edge yz of H with the path y, v0, z yields a Hamilton cycle in D that
proves D is a natural drawing.
The convex version of the Erdős–Szekeres Theorem is an immediate consequence of the
main result of Pach et al. [23]. Their bounds are better than those coming from our Ramsey
argument. Lemma 3.1 and Ramsey’s Theorem also easily prove the convex version of the
Erdős–Szekeres Theorem. We suppose r ≥ 5 is an integer and choose n large enough so
that some subset of V (Kn) of size r is such that every K4 in the Kr is crossing. (For r ≥ 5,
they cannot all be non-crossing.) If the drawing D of Kn is convex, Lemma 3.1 implies
D[Kr] is natural. We state the theorem here for reference.
Theorem 3.4. Let r ≥ 5 be an integer. Then there is an integer N = N(r) such that, if
n ≥ N and D is a convex drawing of Kn, then there is a subgraph J of Kn isomorphic to
Kr such that D[J ] is a natural Kr. 2
The remainder of this section is devoted to a structure theorem for convex drawings.
Let D be a convex drawing of Kn and, for some r ≥ 4, let J be a Kr in Kn such that D[J ]
is natural. We set CJ to be the facial r-cycle in D[J ]. We refer to the face of D[J ] bounded
by CJ as the outside of J and the other side of CJ as the inside of J .
The proof uses the following elementary observations that are somewhat interesting
and otherwise useful in their own right.
Lemma 3.5. Let D be a convex drawing of Kn and, for some r ≥ 4, let J be a Kr such
that D[J ] is natural, with facial r-cycle CJ .
(a) If u is inside J , then, for each v ∈ V (J), D[uv] is inside J .
(b) If u and v are both inside J , then D[uv] is inside J .
(c) If u and v are both outside J and planarly joined to J , then D[uv] is contained in
the outside of J .
(d) Let u be outside of J and suppose there is a vertex v of J such that D[uv] crosses
CJ . Then D[uv] crosses CJ exactly once.
(e) Suppose u is outside of J but, for vertices v and w of J , D[uv] and D[uw] both cross
CJ . Let e and f be the edges of CJ crossed by D[uv] and D[uw]. Then v and w are
in the same component of CJ − {e, f}.
(f) Suppose u is outside of J , v is a vertex of J , and D[uv] crosses CJ on the edge ab.
Then D[ua] and D[ub] are contained in the outside of J .
Proof. We start with (a). If we consider the edges of J incident with v, they partition the
inside of J into discs bounded by 3-cycles. As |V (J)| ≥ 4, the disc containing u is the
convex side of its bounding 3-cycle. Thus, D[uv] is inside this disc and so is inside J .
426 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
For (b), we present an argument suggested by Kasper Szabo Lyngsie that simplifies our
original. There is an edge xy in CJ such that v is in the side ∆ of D[uxy] that has no
vertices of J − {x, y}. If there is an edge of J incident with either x or y that crosses the
3-cycle uxy, then v is in the crossing side of a natural K4 containing u, x, and y. In this
case, ∆ is the convex side of uxy, so D[uv] is inside ∆.
In the other case, let x′ and y′ be the neighbours of x and y, respectively, in CJ − xy.
Then ∆ is contained in the convex side ∆′ of the 3-cycle x′xy, and again D[uv] is contained
in ∆′ and consequently inside J . (We remark that, in fact, D[uv] is contained inside ∆, but
vx or vy might cross uxy, so ∆ need not be the convex side of uxy.)
Moving on to (c), let x, y, z be any three vertices of J and let L be the K5 induced by
u, v, x, y, z. Then D[L] is a convex drawing of K5. Let T be the 3-cycle (x, y, z). The
assumption that u and v are planarly joined to T in D shows that the side ∆T of T that
contains u and v satisfies the Four Point Property in D[L].
Corollary 2.10 implies that D[uv] is contained in ∆T . This is true for every three
vertices of J , so D[uv] is contained in the intersection of all the ∆T ’s; this is precisely the
closure of the face of D[J ] containing D[u] and D[v], as required.
In the proof of (d), we suppose the first crossing of uv is with the edge xy of CJ . The
3-cycle xyv is inside J and, by the definition of drawing, uv cannot cross xyv a second
time.
Turning to (e), we suppose that v and w are in different components of CJ −{e, f} and
that uv crosses e, while uw crosses f . Let x be the end of e in the component of CJ−{e, f}
containing v and let y be the end of f in the component of CJ − {e, f} containing w. By
the definition of drawing, x ̸= v and y ̸= w.
The edge xw crosses uv and the edge yv crosses uw. Moreover, x and y are on different
sides of the 3-cycle uvw, so uvw has no convex side, a contradiction.
For (f), it suffices by symmetry to show D[ua] is outside J . In the alternative, ua
crosses CJ . Since it cannot cross uv by goodness, it must cross the av-subpath of CJ −ab.
But now ua and uv violate (e).
We now turn to the basic ingredient in the structure theorem. Let D be a convex drawing
of Kn and, for some r ≥ 4, let J be a Kr such that D[J ] is natural. The J-induced drawing
J̄ consists of the subdrawing induced by D[J ] and all vertices inside of J . The following
is the main point in the proof of the structure theorem.
Lemma 3.6. Let D be a convex drawing of Kn and, for some r ≥ 4, let J be a Kr such
that D[J ] is natural. If there is a vertex u outside J and a vertex v of J such that D[uv]
crosses CJ , then there is, for some s ≥ 4, a Ks-subgraph J ′ including u such that D[J ′]
is natural and J̄ ⊂ J̄ ′.
Proof. Let ab be the edge of CJ crossed by uv. Lemma 3.5(f) implies that D[ua] and
D[ub] are contained in the outside of J . It follows that, in the av-subpath of CJ −ab, there
is a vertex wa nearest v such that D[uwa] is contained in the outside of J . Likewise, there
is a nearest such vertex wb in the bv-subpath.
For any internal vertex x in the wawb-subpath P of CJ − ab, the edge ux must cross
CJ ; Lemma 3.5(d) and (f) imply ux must cross wawb. It follows that ux does not cross P .
Thus, the cycle consisting of u, together with P , makes the facial cycle for a natural Ks
(s = 1 + |V (P )| ≥ 4) and all the points of J̄ are on or inside this Ks.
Our structure theorem is an immediate consequence of Lemmas 3.5(c) and 3.6.
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 427
Theorem 3.7 (Structure Theorem). Let n ≥ 5 and let D be a convex drawing of Kn. Then,
for some r ≥ 4, there is a Kr-subgraph J such that D[J ] is natural, every vertex outside
of J is planarly joined to J , and any two vertices outside J are joined outside J . 2
As a consequence of the Structure Theorem, we have the following straightforward,
though not trivial, observation. As it is not of immediate interest, we give only a proof
sketch.
Theorem 3.8. Let n ≥ 5 and let D be a drawing of Kn. Suppose that, for every subgraph
J of Kn that is isomorphic to a K4 and D[J ] has a crossing, there are no vertices of Kn
inside D[J ]. Then D[Kn] is convex and either:
1. a natural Kn; or
2. a natural Kn−1 with one vertex outside that is planarly joined to the Kn−1; or
3. the unique drawing of K6 with three crossings.
Proof sketch. The hypothesis on the crossing K4’s implies the drawing is convex: in both
K̃35 and K̃55, there is a crossing K4 with a vertex inside the K4.
Apply the Structure Theorem 3.7 to D to get a subgraph J of Kn such that D[J ] is a
natural Kr, with r ≥ 4 and every other vertex of Kn is either inside D[J ] or is outside J
and planarly joined to J .
Any vertex inside D[J ] is in a face that is incident with a crossing of some crossing K4
involving four vertices in J . Since this is forbidden, there is no vertex inside D[J ].
If there are three vertices of Kn outside D[J ], then there is a crossing K4 with a vertex
inside.
If there are two vertices u, v of Kn outside D[J ] and some edge from u to J crosses
two edges from v to J , then there is a crossing K4 with a vertex inside. In particular, if
r ≥ 5, then there is at most one vertex outside J .
The remaining case is r = 4 and no uJ-edge crosses two vJ-edges and no vJ-edge
crosses two uJ-edges. This is the unique drawing of K6 with three crossings.
In general, if, in a convex drawing of Kn, we bound by a non-negative integer p the
number of vertices allowed inside any natural K4, there is a theorem in the spirit of Theo-
rem 3.8. There are more special cases with n small, but if n is large enough (on the order
of 3p), the structure is: a natural Kr, with r at least roughly p/3, and at most one of the
remaining points is outside the natural Kr.
4 h-convex drawings
In this section, we investigate h-convex drawings. Our main result is a characterization of
h-convex drawings; this immediately yields a polynomial time algorithm for determining
if a drawing is h-convex.
Consider the drawing K116 . It is convex, but not h-convex. To see that it is convex, it
suffices to check the six K5’s and observe that none of them is either K̃35 or K̃55. To see
that it is not h-convex, consider the dashed K4 (including the thick edge) highlighted in
Figure 1. For this K4, either of the 3-cycles T containing the thick edge has its bounded (in
the figure) side convex, while its unbounded side is not convex. A similar statement holds
428 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
for the a 3-cycle in the dotted K4 that contains the thick edge (bounded and unbounded
sides reversing roles). These 3-cycles show that D is not h-convex.
Definition 4.1. Let D be a drawing of Kn and let J and J ′ be distinct K4’s in D such that
both D[J ] and D[J ′] are crossing K4’s. For 3-cycles T and T ′ in J and J ′, respectively,
let ∆T and ∆T ′ be the sides of T and T ′, respectively, not containing the fourth vertex of
J and J ′, respectively. Then J and J ′ are inverted K4’s in D if there are 3-cycles T in J
and T ′ in J ′ such that D[T ] ⊆ ∆T ′ but ∆T ̸⊆ ∆T ′ .
The following observation is immediate from the definition.
Observation 4.2. Let J and J ′ be inverted K4’s in a drawing D of Kn and let T and T ′ be
3-cycles in J and J ′, respectively. Let ∆T and ∆T ′ be the sides of T and T ′, respectively,
not containing the fourth vertex of J and J ′, respectively. If D[T ] ⊆ ∆T ′ but ∆T ̸⊆ ∆T ′ ,
then D[T ′] ⊆ ∆T but ∆T ′ ̸⊆ ∆T .
We are ready for our first characterization of h-convex drawings.
Lemma 4.3. Let D be a convex drawing of Kn. Then D is h-convex if and only if there
are no inverted K4’s.
Proof. It is clear that if D is h-convex, then there are no inverted K4’s.
For the converse, we shall inductively obtain a list C of convex sides, one for each 3-
cycle of Kn. Along the way, the list C will have convex sides for some, but not all, of the
3-cycles of Kn. Such a partial list is hereditary if, for any 3-cycles T and T ′ having convex
sides ∆T and ∆T ′ , respectively, in C, if D[T ] ⊆ ∆T ′ , then ∆T ⊆ ∆T ′ .
Our initial list C0 consists of the convex sides for every 3-cycle that is in a crossing K4.
The assumption that there are no inverted K4’s immediately implies C0 is hereditary.
Let T1, . . . , Tr be the 3-cycles in Kn such that, for i = 1, 2, . . . , r, Ti is not in any
crossing K4. For j ≥ 1, suppose that Cj−1 is a hereditary list of convex sides that includes
C0 and a convex side for each of T1, . . . , Tj−1.
If there is a convex side ∆T ∈ Cj−1 such that D[Tj ] ⊆ ∆T , then we choose ∆Tj so
that ∆Tj ⊆ ∆T . Otherwise, we choose ∆Tj arbitrarily from the two sides of D[Tj ]. Set
Cj = Cj−1 ∪ {∆Tj}.
We show that Cj is hereditary. If not, then, since Cj−1 is hereditary, there is a 3-
cycle T with a convex side ∆T ∈ Cj−1 such that either D[T ] ⊆ ∆Tj and ∆T ̸⊆ ∆Tj or
D[Tj ] ⊆ ∆T and ∆Tj ̸⊆ ∆T . The second case implies that D[T ] ⊆ ∆Tj and ∆T ̸⊆ ∆Tj ,
which is the first case.
Thus, in both cases, we have that D[T ] ⊆ ∆Tj and ∆T ̸⊆ ∆Tj . By the choice of ∆Tj ,
there is a second already considered triangle T ′ such that D[T ′] is contained in the other
side ∆Tj of D[Tj ] but ∆T ′ ̸⊆ ∆Tj .
Evidently, D[T ] ⊆ ∆T ′ and ∆T ̸⊆ ∆T ′ , yielding the contradiction that Cj−1 is not
hereditary.
Lemma 4.3 yields an O(n8) algorithm for determining whether a drawing is h-convex.
Also, a similar argument proves the following analogous fact for f-convexity. This is es-
sentially the characterization of pseudolinearity due to Aichholzer et al. [4].
Theorem 4.4 ([4]). Let D be a drawing of Kn. Then D is f-convex if and only if there
is a face Γ such that, for every isomorph J of K4 for which D[J ] is a crossing K4, Γ is
contained in the face of D[J ] bounded by the 4-cycle. 2
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 429
There is a colourful way to understand this theorem. For each isomorph J of K4 for
which D[J ] is a crossing K4, let CJ be the 4-cycle in J that bounds a face of D[J ]. Paint
the side of D[CJ ] that contains the crossing of D[J ]. If the whole sphere is painted, then
D is not f-convex. Otherwise, with respect to any face F of D[Kn] that is not painted, F
witnesses that D is f-convex.
Our next result gives a surprising characterization of h-convex drawings of Kn by a
single additional forbidden configuration.
Theorem 4.5. Let D be a convex drawing of Kn. Then D is h-convex if and only if, for
each isomorph J of K6 in Kn, D[J ] is not isomorphic to K116 .
Proof. Since h-convexity is evidently inherited by induced subgraphs, no h-convex drawing
of Kn can contain K116 . Conversely, suppose D is not h-convex; we show D contains K116 .
By Lemma 4.3, there exist isomorphs J1 and J2 of K4 that are inverted in D. For
i = 1, 2, let Ti be a 3-cycle in Ji with convex side ∆Ti such that D[T1] ⊆ ∆T2 and
∆T1 ̸⊆ ∆T2 .
Let w be the vertex of J1 not in T1; D[w] is separated from D[T2] by D[T1]. Let x be
the vertex of T1 such that D[wx] crosses D[T1]. Complete D[wx] to a simple closed curve
γ by adding a segment on the non-convex side of D[T1] joining D[w] and D[x]. Clearly
γ separates the two vertices of T1 − x. Moreover, D[T1] and, therefore, D[w] as well, are
all contained in ∆2. Convexity implies D[J1] ⊆ ∆2. Thus, γ also separates one of the
vertices of T1 − x from D[T2]; let z be the one separated from T2 by γ and let y be the
other.
Since D[T1] ⊆ ∆T2 , D[T2 + z] is a non-crossing K4. If any of the edges from z to T2
crosses T1, then we have proof that the side ∆T1 of D[T1] is not convex, a contradiction.
Therefore, D[T1] is contained in a face Γ of D[T2 + z] that is incident with z. It follows
that w is also in Γ.
Let a be the vertex of T2 not incident with Γ. The edge wx has both its ends in Γ. Since
γ separates z from T2, γ must cross za and, therefore, is not contained in Γ. It follows that
Γ is not the convex side of the 3-cycle T3 that bounds Γ.
Evidently, D[T3] ⊆ ∆T2 and ∆T3 ̸⊆ ∆T2 . Corollary 2.5(b) implies that there is a vertex
v3 such that v3 ∈ Γ and D[T3 + v3] is a crossing K4. Because T2 is in the isomorph J2 of
K4, there is a vertex v2 in J2 that is not in T2. Since D[J2] is a crossing K4, D[v2] /∈ ∆T2 .
We now consider the isomorph of K6 consisting of (T2 ∪ T3) + {v2, v3}. Because
D[(T2 ∪ T3) + v2] is contained in ∆T3 , no edge from v2 to a vertex in T2 ∪ T3 can cross
D[T3]. In particular, (recall that a is the vertex of T2 not in T3) D[v2a] does not cross
D[T2 ∪ T3]. Let b be the vertex of T2 such that D[v2b] crosses D[T2] and let c be the third
vertex of T2.
Symmetrically, z is the vertex of T3 that is not in T2, so D[v3z] does not cross
D[T2∪T3]. As both D[z] and D[v2] are in ∆T3 , the edge zv2 cannot cross T3. Since D[v2b]
crosses D[ac] but not D[T3], it must also cross D[az]. It follows that D[v2z] crosses only
D[ac].
Let b′ be the one of b and c such that D[v3b′] crosses D[T3] and let c′ be the other.
There are two cases to consider: b = b′ and c = c′; or b = c′ and c = b′. Note that, in
each case, convexity and the definitions of b and b′ determine the routings of all the edges
except v2v3 and v3a.
Let T4 be the 3-cycle induced by b, v2 and c. Since D[ac] crosses D[v2b], the convex
side of D[T4] is the side that contains v3. Thus, D[v2v3] must be contained in this side of
430 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
D[T4]. In the case b = b′, D[v3b] crosses D[cz], D[zv2], and D[az]. Thus, the only routing
for D[v2v3] is across D[ac] and D[zc]. In the case b = c′, the only routing for D[v2v3]
is across D[ac], D[az], and D[zb]. In both cases there is only one routing available for
D[v3a].
To see in each case that these drawings are both K116 , focus on the face-bounding 4-
cycles induced by b, a′, v3, c and b, a, v2, c.
The previous results were about a drawing being h-convex. The following result char-
acterizes when a collection of sides, one for each 3-cycle of Kn, is a set of h-convex sides.
Its proof is similar to the proof of Theorem 4.5.
Lemma 4.6. Let D be a drawing of Kn and, for each 3-cycle T of Kn, let ∆T be one
of the closed discs bounded by D[T ]. Let C be the set of all these ∆T . Then C is a set of
h-convex sides if and only if both of the following hold:
(1) each ∆T has the Four Point Property; and
(2) for each non-crossing K4, at least three of the four (closed) faces of the non-crossing
K4 are in C.
Proof. Let C be a set of h-convex sides. They are also convex sides, so obviously satisfy
(1). If J is a non-crossing K4 and T is a 3-cycle in J , then the side ∆T of T that is in C is
either empty or contains J ; in the latter case all the empty sides of the other 3-cycles in J
are in C by heredity. Thus, at most one of the four 3-cycles in J has non-empty side in C,
which is (2).
Conversely, let C satisfy (1) and (2). Then C is a set of convex sides by Corollary 2.4.
Now let T, T ′ be 3-cycles such that D[T ′] ⊆ ∆T .
Suppose there is a t ∈ T \ T ′ such that T ′ + t is a crossing K4. Then the convex
side ∆T ′ of T ′ is the side that does not contain t. Because D[T ′] ⊆ ∆(T ), this implies
∆T ′ ⊆ ∆(T ), as required. Thus, we may assume T ′ is not crossed in D.
Let v be any vertex of T \T ′. Then D[T + v] is a non-crossing K4. By (2), each of the
three faces of D[T + v] incident with v is the side of the bounding 3-cycle that is in C.
We proceed by induction on the number of vertices of T ′ that are not in T ; this number
being at least 1. Because T ′ is not crossed in D, the remaining vertices of T ′ are either in
or incident with the same face F of T + v. Let T ′′ be the 3-cycle bounding F .
The base of the induction is that T ′− v ⊆ T . In this case, T ′ = T ′′ and ∆T ′ is F ; thus,
∆T ′ ⊆ ∆T , as required.
For the induction step, suppose |T ′ \ T | ≥ 2. We have already seen that the 3-cycle
T ′′ bounding F has ∆T ′′ = F . For this induction step, there is a vertex w of T ′ in the
interior of F , so the side of ∆T ′′ in C is not a face of T ′′ + w. Now T ′ ⊆ ∆T ′′ and
|T ′ \ T ′′| < |T ′ \ T |. By induction, ∆T ′ ⊆ ∆T ′′ . Since ∆T ′′ ⊆ ∆T , we have shown C is
the set of h-convex sides, as required.
Although Lemma 4.6 shows that h-convexity is determined by considering all sets of
four points, it is not evident that there is an O(n4) algorithm to test whether a drawing is
h-convex. Theorem 4.5 makes it clear that there is an O(n6) algorithm to determine if a
drawing of Kn is h-convex.
It is O(n4) to check that a drawing is convex. To see this, we use the Four Point Property
(Corollary 2.4): for each 3-cycle T and each vertex v, we determine which side of T v is
on and whether T + v is a planar K4.
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 431
We conclude this section with an observation related to the Structure Theorem 3.7.
Lemma 4.7. Let D be an h-convex drawing of Kn consisting of a natural Kr (with r ≥ 4)
and all other points inside the natural Kr. Then D is f-convex.
Proof. Any triangle of the Kr has its convex side determined; it is the side that avoids the
face F bounded by the cycle Cr. Let T be any other triangle. If an edge of Kr crosses T ,
then the convex side of T must also avoid F . If this does not happen, then T is inside a
triangle of Kr and the result follows from the hereditary property.
5 Suboptimal drawings of Kn having either K̃35 or K̃
5
5
In this section, we prove that a broad class of “locally determined” drawings of Kn are
suboptimal. This is the first theorem of its type. The theorem requires the presence of
either K̃35 or K̃55 in the drawing, but, for at least one such K5, the occurrence is restricted.
This might be a first step towards showing that all optimal drawings of Kn are convex.
This line of research was stimulated by Tilo Wiedera’s computation (personal commu-
nication) showing that any drawing of K9 that contains a K̃55 has at least 40 crossings. This
is in line with Aichholzer’s later computations (see the remark following the statement of
Theorem 5.1 below).
We also rethink the approach in [21] that cr(K9) = 36. This was done before convexity
became known to us. Using the fact that cr(K7) = 9, it is easy to see that cr(K9) ≥ 34. At
the end of this section, we show easily by hand that there is no non-convex drawing D of
K9 such that cr(D) = 34. Thus, to prove that cr(K9) = 36, it suffices to consider convex
drawings of K9.
A principal result of this work is the following, which shows that if D is a drawing of
Kn such that some non-convex K5 intersects every other non-convex K5 in at most two
vertices, then D is not optimal.
Theorem 5.1. Let D be a drawing of Kn such that there is an isomorph J of K5 with D[J ]
either K̃35 or K̃55. Suppose, for every isomorph H of K7 in Kn containing J , D[J ] is the
only non-convex K5 in D[H].
1. If J is K̃35, then there is a drawing D′ of Kn such that cr(D′) ≤ cr(D)− 2.
2. If J is K̃55, there is a drawing D′ of Kn such that cr(D′) ≤ cr(D)−4. If, in addition,
n is even, then cr(D′) ≤ cr(D)− 5.
We remark that the lower bounds 2, 4, and 5 for cr(D) − cr(D′) exhibited in Theo-
rem 5.1 are precisely the smallest differences found by Aichholzer (private communica-
tion) between any drawing, for n ≤ 12, of Kn that has either a K̃35 or a K̃55 and an optimal
drawing of Kn.
Proof of Theorem 5.1. We use the labelling of J as shown in Figure 4. We first deal with
the case J = K̃35.
(I) J = K̃35 .
Claim 5.2. There is no vertex of D[Kn] in the side of any of the 3-cycles D[stw], D[suv],
and D[tuv] that has no vertex of D[J ].
432 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
Figure 4: Labelled K̃35 and K̃55 for the proof of Theorem 5.1.
Proof of Claim 5.2. We start with D[stw]. Similar arguments apply to D[suv]. Finally,
symmetry shows that D[tuv] also does not have a vertex on the side empty in D[J ].
Suppose to the contrary that there is a vertex x of Kn such that D[x] is in the side of
D[stw] that is empty in D[J ]. By hypothesis, the K5 consisting of J −w plus x is convex
in D. Since D[x] is incident with a face of D[J − w] that is incident with the crossing of
D[J −w], Observation 2.1 and convexity imply D[xu] does not cross the 4-cycle D[stuv].
Likewise, the K5 consisting of J − v together with x is convex in D. Again, D[x] is in
a face of D[J − v] incident with a crossing, so D[xu] does not cross the 4-cycle D[wtus].
However, D[x] and D[u] are in different faces of D[stuv]∪D[wtus], so D[xu] must cross
at least one of the two 4-cycles.
The same deletions show that any vertex in the empty side of D[suv] cannot connect to
t.
There are two remaining regions of interest. Let × be the crossing of su with tv. Let
R1 be the region bounded by D[wt×sw] that does not contain D[u] and D[v]; R2 is the
region bounded by D[stuv] that does not contain D[w].
The following observations follow immediately from the convexity of the correspond-
ing K5 and the knowledge of the crossings.
(Obs. 1) If x ∈ R1, then J − w + x is convex, so the routings of x to s, t, u, v are
determined.
(Obs. 2) If y ∈ R2, then J−u+y and J − v + y are convex, so the routings of y to
J are determined.2
These observations yield all of (1) – (5) in the following assertions except for (3).
Claim 5.3. If D[x] ∈ R1 and D[y] ∈ R2, then:
(1) D[xu] crosses D[J ] only on D[tv] and D[xv] crosses D[J ] only on D[su];
(2) D[xs] and D[xt] do not cross D[J ];
(3) D[xw] either does not cross D[J ], or crosses D[st] and at least one of D[su] and
D[tv];
(4) D[ys], D[yt], D[yu], and D[yv] cross D[J ] at most in either D[uw] or D[vw] (or
both);
(5) D[yw] crosses only D[st].
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 433
Moreover, if zz′ is an edge of G with neither z nor z′ in J and T is one of the 3-cycles
stw, suv, and tuv, then either D[zz′] does not cross D[T ] or it crosses the one of D[st],
D[su], and D[tv] that is in D[T ].
Proof of Claim 5.3. For xw, the following argument is due to Matthew Sullivan, simplify-
ing our original. Consider the isomorph L of K2,4 with x and w on one side and s, t, u, v
on the other side. Then D[xw] does not cross (the planar drawing) D[L] and so is contained
in one of the four faces of D[L]. The face of D[L] bounded by swtx is disjoint from D[J ].
In each of the other three faces, D[xw] must cross D[st]. In two of these three faces, it also
crosses exactly one of D[su] and D[tv]. In the third, it crosses both D[su] and D[tv].
For the moreover, we consider the remaining three types of edges z1z2: D[z1] and
D[z2] can both be in R1; both in R2; or one in each. In all three cases for z1, z2 and
all three cases for the three-cycle T , D[z1] and D[z2] are on the same side of D[T ]. In
the event that D[z1] and D[z2] are both planarly joined to D[T ], Corollary 2.10 applies to
show D[z1z2] does not cross the 3-cycle.
In the remaining cases, we assume that D[z1] is not planarly joined to D[T ]. If T =
stw, then Claim 5.3(3) and (5) imply the only possible crossing with D[T ] is D[z1w]
crossing D[st]. As D[z1z2] has either 0 or 2 crossings with D[stw], but does not cross
D[z1w], the two crossings of D[z1z2] and D[T ] cannot be on D[ws] and D[wt]. For
T = suv and T = tuv, the edges z1u and z1v, respectively, produce analogous results.
We are now prepared for the final part of the proof. For i = 1, 2, let ri be the number
of vertices of D[Kn] that are in (the interior of) Ri.
Let D′ be the drawing of Kn obtained from D by making the following two changes:
(C1) reroute st alongside the path D[swt], so as to not cross D[wu] and D[wv]; and
(C2) reroute su alongside the path D[svu] so as to cross D[vw].
We first consider the changes in crossings arising from rerouting st. There are at least
2+ r2 crossing pairs of edges in D that do not cross in D′: two from D[st] crossing D[wv]
and D[wu], plus all the crossings of D[st] from those edges incident with D[w] that cross
D[st]. There are at least r2 of these latter crossings, as every vertex z such that D[z] is in
R2 has D[zw] crossing D[st].
On the other hand, there is a set of at most r1 crossing pairs in D′ that do not cross
in D. These arise from the the edges joining a vertex drawn in R1 to D[w]; these might
not intersect D[J ]. Those that do intersect D[J ] cross D[st] and, therefore, yield further
savings.
We show that every other edge z1z2 has no more crossings in D′ than it has in D.
Case 1: z1, say, is in J .
In this case, we use Claim 5.3. Items (1), (2), (4), and (5) show that no such edge has
more crossings in D′ than in D, except possibly xw.
If D[xw] does not cross D[J ], then D′[xw] also does not cross D′[J − st], as required.
If D[xw] crosses D[J ], then Claim 5.3(3) implies that D[xw] crosses D[st]. Thus, D[xw]
crosses both D[su] and one of D[sv] and D[tu]; in this case, the same is true of D′[xw] in
D′, as required.
Case 2: neither z1 nor z2 is in J .
434 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
If D[z1z2] crosses the 3-cycle D[stw], then the moreover part of Claim 5.3 shows it
crosses D[st]. Therefore, it crosses exactly one of D[sw] and D[wt], showing that D′[z1z2]
crosses D′[st] and the same one of D′[sw] and D′[wt]. That is, z1z2 crosses the same two
edges in both drawings, and we are done.
The net result is that the rerouting of st contributes at least 2 + (r2 − r1) to cr(D) −
cr(D′).
Now we turn our attention to the changes in crossings from rerouting su. The crossing
of D[su] with D[tv] is replaced by a crossing of D′[su] with D′[vw]. In addition, r2 edges
incident with v do not cross D[su], but cross D′[su], while r1 edges incident with v cross
D[su], but do not cross D′[su].
The only additional remark special to this rerouting is the observation that, for z in
R1, Claim 5.3 implies that if D[zw] crosses the 3-cycle D[suv], then zw crosses su. This
shows that D′[zw] also crosses D′[suv] twice, so there are no other “new” crossings.
Therefore, the su rerouting contributes at least r1 − r2 to the difference cr(D) −
cr(D′). Combining this with the contribution from st, we get that cr(D) − cr(D′) ≥
(2 + r2 − r1) + (r1 − r2) = 2. That is, cr(D′) ≤ cr(D)− 2, as required.
(II) J = K̃55 .
In this case, there is a homeomorphism Θ of the sphere to itself that is an involution
that restricts to J as, using the labelling in Figure 4: s ↔ w; t ↔ v; and u is fixed. This
will be helpful at several points in the following discussion. The outline of the argument is
the same as for K̃35, but there are some interesting differences.
Let R1 be the face of D[J ] incident with all three points in D[{s, t, u}] (the unbounded
face in the diagram) and let R2 be the face of D[J ] incident with all three points in
D[{u, v, w}] (note that R2 = Θ(R1)).
Claim 5.4. If z is a vertex of Kn not in J , then D[z] ∈ R1 ∪R2.
Proof of Claim 5.4. Suppose x is a vertex of Kn−V (J) such that D[x] is not in R1 ∪R2.
Suppose first that D[x] is in the region bounded by the 4-cycle D[wtsv].
The convexity of D[(J − s) + x] and of D[(J − w) + x] imply that D[xu] does not
cross the 4-cycles D[twvu] and D[stuv], respectively. However, D[x] is not in a face of
D[twvu] ∪D[stuv] incident with D[u], a contradiction.
The remaining possibility is that D[x] is in the face F that is both distinct from R1 and
either incident with D[ut] or, symmetrically, incident with uv; we assume the former. The
convexity of D[(J−t)+x] and D[(J−v)+x] show that D[xw] does not cross the 4-cycles
D[swvu] and D[swut], respectively. However, D[x] is not in a face of D[swvu]∪D[swut]
incident with D[w], a contradiction.
We next move to the routings of the edges from a vertex D[x] in R1 ∪R2 to D[J ].
Claim 5.5. If D[x] ∈ R1, then:
(1) D[xu] and D[xs] do not cross D[J ];
(2) D[xv] crosses D[J ] only on D[uw], and D[xw] crosses D[J ] only on D[sv] and
D[tv]; and
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 435
(3) D[xt] either does not cross D[J ] or it crosses D[J ] precisely on D[sv], D[sw], and
D[su].
Furthermore, if D[x], D[x′] ∈ R1, then D[xx′] ⊆ R1.
Proof of Claim 5.5. The convexity of D[(J−t)+x] and D[(J−u)+x] shows D[xs] does
not cross the 4-cycles D[suvw] and D[stwv], respectively. The convexity of J − s + x
shows xu does not cross J − s. Also xu does not cross su by simplicity, so xu does not
cross any edge incident with s.
The convexity of J − t+ x shows xv, respectively xw, crosses J − t only uw, respec-
tively tv. Also xv, respectively xw, does not cross vt, respectively wt, by simplicity, so
xv, respectively xw, does not cross any edge incident with t.
The convexity of D[(J − s) + x] determines the routing of D[xt], except with respect
to D[s], leaving the two options described.
For the furthermore conclusion, D[x] and D[x′] are planarly joined to the 3-cycle
D[svu]. Corollary 2.10 shows that D[xx′] is disjoint from D[svu]. In the same way,
D[xx′] is disjoint from D[swu], and D[tvu]. Thus, D[xx′] can only cross D[J ] on D[st].
However, letting × denote the crossing of D[su] with D[tv], D[xx′] must cross the 3-cycle
D[st×] an even number of times and it can only cross it on D[st], which is impossible.
The homeomorphism Θ implies a completely symmetric statement when x ∈ R2. We
provide it here for ease of reference.
Claim 5.6. If D[x] ∈ R2, then, in D[J + x]:
(1) D[xu] and D[xw] do not cross D[J ];
(2) D[xt] crosses D[J ] only on D[us], and D[xs] crosses D[J ] only on D[tw] and
D[tv]; and
(3) D[xv] either does not cross D[J ] or it crosses D[J ] precisely on D[wt], D[ws], and
D[wu].
Furthermore, if D[x], D[x′] ∈ R2, then D[xx′] ⊆ R2.
Using the homeomorphism Θ, we may choose the labelling of J so that the number r1
of vertices of D[Kn] drawn in R1 is at most the number r2 drawn in R2.
Our next claim was somewhat surprising to us in the strength of its conclusion.
Claim 5.7. If there is a vertex x of Kn − V (J) such that D[x] ∈ R1 and D[xt] crosses
D[sv], D[sw], and D[su], then there is a drawing D′ of Kn such that cr(D′) ≤ cr(D)− 4
and, if n is even, cr(D′) ≤ cr(D)− 5.
Proof of Claim 5.7. Choose such an x so that D[xt] crosses D[sv], D[sw], and D[su] and
such that, among all such x, the crossing of D[xt] with D[sv] is as close to D[s] on D[sv]
as possible. Let ∆ be the closed disc bounded by the 3-cycle D[sxt] that does not contain
the vertices D[{v, u, w}].
If there is a vertex y of Kn such that D[y] is in the interior of ∆, then D[y] is in the
face of D[J + x] contained in ∆ and incident with D[sx]. However, the convexity in D of
(J − {u,w}) + {x, y} implies D[yt] crosses D[sv] closer to s in D[sv] than D[xt] does,
contradicting the choice of x. Therefore, no vertex of D[Kn] is in ∆.
436 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
The drawing D′ is obtained from D by rerouting xt to go alongside the path D[xst],
on the side not in ∆. (That is, D[xt] is pushed to the other side of D[s].)
The hardest part of the analysis of the crossings of D′ compared to D is determining
what happens to an edge of D[Kn] that crosses D[st]. No edge of D[J ] crosses D[st].
Claims 5.5 and 5.6 imply that: no edge from a vertex in R1 ∪ R2 to a vertex in D[J ]
crosses D[st]; and no edge with both incident vertices in the same one of R1 or R2 crosses
D[st]. Thus, the only possible crossing of D[st] is by an edge D[yz], with D[y] ∈ R1 and
D[z] ∈ R2.
Because of the routing of D[sz], D[yz] cannot also cross D[xs]. Therefore, D[yz] also
crosses D[xt]. It follows that such an edge has the same number of crossings of xt in
both D and D′. Therefore, any edge that crosses D[xs] crosses D[xt] and so has the same
number of crossings with D[xt] and D′[xt].
The only changes then are in the number of crossings of D[xt] with edges incident
with D[s] and the number of crossings with D[J ]. There are 3 fewer of the latter. From
R1 to D[s], there are at most r1 − 1 crossings of D′[xt]. From R2 to D[s], we have lost
r2 crossings of D[xt]. Thus, D′ has at least (r2 − (r1 − 1)) + 3 = (r2 − r1) + 4 fewer
crossings than D. This proves the first conclusion.
Since n = 5 + r1 + r2, if n is even, then r1 ̸= r2 and, therefore, r2 − r1 ≥ 1. In this
case D′ has at least 5 fewer crossings, as claimed.
It follows from Claim 5.7 that we may assume that, for D[x] ∈ R1, D[xt] is disjoint
from D[J ]. Combining this with the other information from Claim 5.5, we may assume the
following property.
R1 Assumption: If D[x] ∈ R1, then D[x] is planarly joined to D[J − w].
Let D′ be obtained from D by rerouting D[tv] on the other side of the path D[tsv].
There are two claims that complete the proof of Theorem 5.1. The first, similar to Claim 5.7,
shows that there are at least 2 fewer crossings in D′ (3 if n is even). The second shows that
D′ satisfies the hypotheses of Theorem 5.1. Therefore, there is a third drawing D′′ with at
least two fewer crossings than D′, as required.
Claim 5.8. cr(D′) ≤ cr(D)− ((r2 − r1)− 2).
Proof of Claim 5.8. The proof is very similar to that of Claim 5.7. The main point is to
see that no edge e can have D[e] cross both D[ts] and D[sv]. Let x be incident with e.
If D[x] ∈ R2, then the routing of D[xs] is known; since D[xs] does not cross D[e], the
crossings of D[e] with D[ts] and D[sv] are joined by an arc of D[e] outside D[stuv]. But
then D[e] has both ends in J ∪R2. This contradicts Claim 5.6, so D[x] /∈ R2.
Likewise, Claim 5.5 shows D[x] /∈ R1 and clearly e is not in J . Therefore, there is no
such e.
It is now easy to see that there are (r2 − r1) + 2 fewer crossings of D′[tv] with edges
incident with s than there are of D[tv]. All other crossings of D′[tv] pair off with crossings
of D[tv].
Finally, we show that the drawing D′ satisfies the hypotheses of Theorem 5.1. It is
routine to verify that D′[J ] is K̃35. Now let N be a K5 in Kn such that N ∩ J has 3 or 4
vertices.
If any of s, t, v is not in N , then D′[N ] is homeomorphic to D[N ] and so is convex.
Thus, we may assume s, t, v are all in N .
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 437
Case 1: N ∩ J has four vertices.
In this case, there is a vertex x not in J such that N is either (J−w)+x or (J−u)+x.
If D[x] is in R1, then the routings are determined and we can see by inspection that D′[N ]
is, respectively, the K5 with 1 crossing or the convex K5 with 3 crossings.
If D[x] ∈ R2, then Claim 5.6 shows that D′[(J −w) + x] is the K5 with one crossing.
However, Claim 5.6(3) shows D′[(J − u) + x] has two possibilities for xv, depending on
which way around w it goes. If it crosses both wt and ws, then the drawing is the natural
one. The alternative is to reroute it to not cross D′[N − x]. In this case, Observation 2.8
shows D′[N ] is convex.
Case 2: N ∩ J has 3 vertices.
In this case N = (J − {u,w}) + {x, y}. Since D[x], D[y] ∈ R1 ∪ R2, they are both
on the same side of D[stv]. The routings from either to D[J ] are determined by Claims 5.5
and 5.6 and the assumption following the proof of Claim 5.7. Only when D[x] and D[y]
are in different ones of R1 and R2 is it possible that D[xy] crosses D[stv].
We consider the three possibilities for D[x] and D[y].
Subcase 2.1: D[x] ∈ R1 and D[y] ∈ R2.
All routings in D′[N ] are determined except for D[xy]. The 4-cycle D[xvyt] is un-
crossed in D[N−xy]. As D is a drawing, D[xy] does not cross D[xvyt]. Therefore, either
D[xvyt] or D[xvy] is a face of D′[N ], showing D′[N ] is convex.
Subcase 2.2: D[x] and D[y] are both in R2.
Since D[x] and D[y] are both planarly joined to D′[stv] and D[xy] does not cross
D′[stv], D′[stv] bounds a face of D′[N ]. Thus, D′[N ] is convex.
Subcase 2.3: D[x], D[y] are both in R1.
Suppose D′[N ] is not convex. Then Corollary 2.5(a) implies there is a 3-cycle T in
N such that the two vertices z, z′ of N not in T are in different faces of D′[T ] and both
D′[T + z] and D′[T + z′] are crossing K4’s.
Since both x and y are in the same face of D′[stv], T ̸= stv. If a ∈ {s, t, v}, then the
routings of the edges from x and y to stv show that the two vertices in {s, t, v} \ {a} are
on the same side of D′[xya], so xya ̸= T . The only remaining possibility is that T has x,
say, and two of s, t, v.
Claim 5.9. The 3-cycle D′[tvx] has no convex side.
Proof of Claim 5.9. In the alternative, T is either stx or svx. These two situations are
very similar, so we treat only stx, leaving the completely analogous argument for svx to
the reader. Our strategy is to show that assuming that stx has no convex side in D′ implies
that tvx has no convex side in D′ either.
The vertices v and y are on different sides of D′[stx] and D[vt] crosses D[sx], showing
that the side of D′[stx] containing D[v] is not convex. The edge D[sx] also shows that the
side of D′[tvx] containing D[s] is not convex.
Likewise, there is an edge e incident with y to one of s, t, and x such that D[e] crosses
D′[stx]. Notice that D[xy] does not cross D[xs] and D[xt] by definition of drawing and
D[xy] does not cross D[st] by the R1 Assumption. Therefore, D[xy] does not cross D[st]
and we conclude that D[xy] does not cross D[stx].
438 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
Next suppose that that D[yt] crosses D[xs]. The R1 Assumption shows that D[yt] does
not cross D[stv] and so D[yt] crosses D[vx]. Therefore, this side of D′[tvx] is also not
convex. Combined with the second paragraph of this proof, D′[tvx] is not convex.
In the final case, D[ys] crosses D[xt]. As we traverse D[ys] from D[y], there is the
crossing with D[xt]. A point of D[ys] just beyond this crossing is on the other side of
D[tvx] from both y and s.
The edge D[yv] is contained on the same side of the 3-cycle D[sty] as D[v]. Therefore,
D[yv] must also cross D[xt], showing that the D[y]-side of D[tvx] is also not convex, as
required.
Notice that D[y] is in one side of D′[tvx] and D[s] is on the other. Since s /∈ {t, v, x, y},
D[{t, v, x, y}] and D′[{t, v, x, y}] are homeomorphic. Thus, the side of D[tvx] that con-
tains D[y] is not convex in D.
On the other hand, we know that, in D, D[w] is on the other side of D[tvx] from
D[y]. However, Claim 5.5(2) shows that D[wx] crosses D[tv]. This shows that the side of
D[tvx] containing D[w] is not convex. Combined with the preceding paragraph, the K5
induced by t, v, w, x, y is not convex in D, contradicting the hypothesis of the theorem.
This completes the proof of Subcase 2.3 and the theorem.
It would be significant progress to prove some analogue of Theorem 5.1 with a weaker
hypothesis on extensions J . Indeed, one might expect that no hypothesis beyond the exis-
tence of J is required, as is easily verified for n = 7 (Lemmas 7.5 and 7.7 [21] prove this
for K7 as a simple consequence of the theory developed).
Suppose a drawing D of K8 has a non-convex K5. This K5 is in three different K7’s,
each having at least 11 crossings. Lemma 5.10 below shows D has at least 20 crossings, in
agreement with Aichholzers’s computations.
Lemma 5.10. Let n be an integer, n ≥ 4, and let D be a drawing of Kn. Then
(n− 4) cr(D) =
∑
v∈V (Kn) cr(D − v).
A similar argument shows that a non-convex drawing of K9 cannot have 34 crossings.
Let J be any non-convex K5 in a drawing D of K9 having 34 crossings. Then J is con-
tained in four K8’s in the K9. The preceding paragraph shows each of these K8’s has at
least 20 crossings. Lemma 5.10 and the assumption that D has only 34 crossings shows
that the five remaining K8’s are optimal and hence convex. Thus, J is the only non-convex
K5 in D and so the hypothesis of Theorem 5.1 trivially holds.
The hypothesis of Theorem 5.1 is stronger than we would like and stronger than needed
for the preceding argument for K8. It is not so strong, however, as to force a single non-
convex K5 in a drawing. For example, we have a drawing of K8—a modified TC8—having
two different non-convex K5’s and satisfying the hypotheses of Theorem 5.1.
6 Questions and conjectures
We conclude with a few questions and conjectures.
1. In Section 1 we presented a table with the convexity hierarchy. One obvious omission
is a forbidden drawing characterization of when an h-convex drawing is f-convex.
We pointed out that TC8 is one example of h-convex that is not f-convex. Rerouting
some of the edges between the central and outer crossing K4’s produces a few more
examples.
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 439
Question 6.1. Is there a characterization by forbidden subdrawings of those h-convex
drawings of Kn that are f-convex?
2. The deficiency δ(D) of a drawing D of Kn is the number cr(D)−H(n). The drawing
D has the natural deficiency property if, for every vertex v of Kn, δ(D−v) ≤ 2δ(D).
If the Hill Conjecture is true for n = 2k + 1, then every drawing of K2k has the
natural deficiency property. We prove this in the Appendix.
Conjecture 6.2. For every k ≥ 2, every simple drawing of K2k has the natural
deficiency property.
This seems to be an interesting weakening of the Hill Conjecture; it came up tangen-
tially in the proof that cr(K13) > 217 [20].
3. Pach, Solymosi, and Tóth [23] proved that, for each positive integer r, there is an
N(r) = O(2r
8
) such that, for every n ≥ N(r), every drawing D of Kn contains
either the natural Kr or the Harborth Kr [15]. If D is convex, then it must be the
natural Kr.
Question 6.3. Can the O(2r
8
) bound be improved for convex drawings?
4. The big question is: Is every optimal drawing of Kn convex? While we believe this
is quite conceivable, Ramsey theory suggests other possibilities. Hedging our bets,
we have the following conjecture.
Conjecture 6.4. Exactly one of the following holds:
(a) for all n ≥ 5, no optimal drawing of Kn contains K̃55; and
(b) for any p ≥ 1 and any drawing D of Kp, there is some n ≥ p and an optimal
drawing of Kn (or at least one with at most H(n) crossings) that contains
D[Kp].
ORCID iDs
Alan Arroyo https://orcid.org/0000-0003-2401-8670
R. Bruce Richter https://orcid.org/0000-0002-1444-9699
References
[1] B. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and B. Vogtenhuber, Non-
shellable drawings of kn with few crossings, in: 26th Annual Canadian Conference
on Computational Geometry CCCG 2014, 2014 pp. 46–51, https://www.cccg.ca/
proceedings/2014/.
[2] O. Aichholzer, Rotation systems with specific drawings of K5, in preparation.
[3] O. Aichholzer, T. Hackl, A. Pilz, P. Ramos, V. Sacristán and B. Vogtenhuber, Empty triangles
in good drawings of the complete graph, Graphs Comb. 31 (2015), 335–345, doi:10.1007/
s00373-015-1550-5.
[4] O. Aichholzer, T. Hackl, A. Pilz, G. Salazar, and B. Vogtenhuber, Deciding monotonicity of
good drawings of the complete graph, in: XVI Spanish Meeting on Computational Geometry
(EGC 2015), 2015 pp. 33–36, http://www.ist.tugraz.at/cpgg/publications.
php.
440 Ars Math. Contemp. 22 (2022) #P3.04 / 415–441
[5] A. Arroyo, D. McQuillan, R. B. Richter and G. Salazar, Levi’s lemma, pseudolinear drawings
of Kn, and empty triangles, J. Graph Theory 87 (2018), 443–459, doi:10.1002/jgt.22167.
[6] A. Arroyo, R. B. Richter and M. Sunohara, Extending drawings of complete graphs into ar-
rangements of pseudocircles, SIAM J. Discrete Math. 35 (2021), 1050–1076, doi:10.1137/
20m1313234.
[7] J. Balogh, B. Lidický and G. Salazar, Closing in on Hill’s conjecture, SIAM J. Discrete Math.
33 (2019), 1261–1276, doi:10.1137/17m1158859.
[8] I. Bárány and Z. Füredi, Empty simplices in Euclidean space, Can. Math. Bull. 30 (1987),
436–445, doi:10.4153/cmb-1987-064-1.
[9] I. Bárány and P. Valtr, Planar point sets with a small number of empty convex polygons, Stud.
Sci. Math. Hung. 41 (2004), 243–266, doi:10.1556/sscmath.41.2004.2.4.
[10] L. Beineke and R. Wilson, The early history of the brick factory problem, Math. Intell. 32
(2010), 41–48, doi:10.1007/s00283-009-9120-4.
[11] W. E. Bonnice, On convex polygons determined by a finite planar set, Am. Math. Mon. 81
(1974), 749–752, doi:10.2307/2319566.
[12] P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ.
Sci. Budap. Rolando Eötvös, Sect. Math. 3-4 (1961), 53–62, https://users.renyi.hu/
˜p_erdos/Erdos.html.
[13] R. K. Guy, Crossing numbers of graphs, in: Y. Alavi, D. R. Lick and A. T. White (eds.), Graph
Theory and Applications, Springer Berlin Heidelberg, Berlin, Heidelberg, 1972 pp. 111–124,
doi:10.1007/bfb0067363.
[14] F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinb. Math.
Soc., II. Ser. 13 (1963), 333–338, doi:10.1017/s0013091500025645.
[15] H. Harborth, Empty triangles in drawings of the complete graph, Discrete Math. 191 (1998),
109–111, doi:10.1016/s0012-365x(98)00098-3.
[16] H. Harborth and I. Mengersen, Drawings of the complete graph with maximum number of
crossings, in: Proceedings of the Twenty-Third Southeastern International Conference on Com-
binatorics, Graph Theory, and Computing (Boca Raton, FL, 1992), Congr. Numer. 88, pp.
225–228, 1992.
[17] D. J. Kleitman, A note on the parity of the number of crossings of a graph, J. Comb. Theory,
Ser. B 21 (1976), 88–89, doi:10.1016/0095-8956(76)90032-0.
[18] F. Levi, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Math.-Phys.
Kl. Sächs. Akad. Wiss. Leipzig 78 (1926), 256–267.
[19] J. Matousek, Intersection graphs of segments and ∃R2, 2014, arXiv:1406.2636
[math.CO].
[20] D. McQuillan, S. Pan and R. B. Richter, On the crossing number of K13, J. Comb. Theory, Ser.
B 115 (2015), 224–235, doi:10.1016/j.jctb.2015.06.002.
[21] D. McQuillan and R. B. Richter, On the crossing number of Kn without computer assistance,
J. Graph Theory 82 (2016), 387–432, doi:10.1002/jgt.21908.
[22] N. E. Mnëv, The universality theorems on the classification problem of configuration varieties
and convex polytopes varieties, in: Topology and Geometry—Rohlin Seminar, Springer, Berlin,
volume 1346 of Lecture Notes in Math., pp. 527–543, 1988, doi:10.1007/bfb0082792.
[23] J. Pach, J. Solymosi and G. Tóth, Unavoidable configurations in complete topological graphs,
Discrete Comput. Geom. 30 (2003), 311–320, doi:10.1007/s00454-003-0012-9.
A. Arroyo et al.: Convex drawings of the complete graph: topology meets geometry 441
[24] A. Suk, On the Erdős-Szekeres convex polygon problem, J. Am. Math. Soc. 30 (2017), 1047–
1053, doi:10.1090/jams/869.
[25] U. Wagner, On a geometric generalization of the upper bound theorem, in: 2006 47th Annual
IEEE Symposium on Foundations of Computer Science (FOCS’06), 2006 pp. 635–645, doi:
10.1109/focs.2006.53.
Appendix
Here we prove the claim made in the discussion about the natural deficiency property,
related to Conjecture 6.2: if the Hill Conjecture is true for n = 2k+ 1, then every drawing
of K2n has the natural deficiency property.
Let D be a simple drawing of K2n, let v be any vertex of K2n, and let r(v) denote
the total number of crossings in D involving edges incident with v. Duplicating v to get
the drawing D + v of K2n+1, we get cr(D + v) = cr(D) + W (2n − 1) + r(v), where
W (m) = ⌊m2 ⌋⌊
m−1
2 ⌋ is the smallest number of crossings in a drawing of K2,m such that
the vertices on the 2-side have the same clockwise rotation of the m remaining vertices.
By assumption, cr(D+v) ≥ H(2n+1), so H(2n+1) ≤ cr(D)+W (2n−1)+ r(v).
On the other hand, arithmetic shows that H(2n+ 1) = H(2n) +W (2n− 1) + (H(2n)−
H(2n− 1)). Therefore,
2H(2n) +W (2n− 1)−H(2n− 1) = H(2n+ 1)
≤ cr(D) +W (2n− 1) + r(v) .
Cancelling the common W (2n− 1) and rearranging yields
r(v) +H(2n− 1) ≥ 2H(2n)− cr(D) . (A.1)
Inequality (A.1) implies
δ(D − v) = cr(D − v)−H(2n− 1)
= cr(D)− r(v)−H(2n− 1)
≤ 2 cr(D)− 2H(2n)
= 2δ(D) ,
as claimed.