ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P2.10
https://doi.org/10.26493/1855-3974.2763.1e6
(Also available at http://amc-journal.eu)
There is a unique crossing-minimal rectilinear
drawing of K18*
Bernardo M. Ábrego , Silvia Fernández–Merchant
Departament of Mathematics, California State University at Northridge,
CA, United States
Oswin Aichholzer
Institute for Software Technology, University of Technology, Graz, Austria
Jesús Leaños †
Academic Unit of Mathematics, Autonomous University of Zacatecas, Mexico
Gelasio Salazar
Institute of Physics, Autonomous University of San Luis Potosi, Mexico
Received 8 December 2021, accepted 15 June 2023, published online 14 February 2024
Abstract
We show that, up to order type isomorphism, there is a unique crossing-minimal recti-
linear drawing of K18. It is easily verified that this drawing does not contain any crossing-
minimal drawing of K17. Therefore this settles, in the negative, the following question
from Aichholzer and Krasser: is it true that, for every integer n ≥ 4, there exists a crossing-
minimal drawing of Kn that contains a crossing-minimal drawing of Kn−1?
Keywords: Rectilinear crossing number, complete graphs, k-edges.
Math. Subj. Class. (2020): 05C10, 05C60
*We thank an anonymous referee for carefully reading an earlier version of this paper, and providing several
insightful comments, corrections, and suggestions.
†Corresponding author.
E-mail addresses: bernardo.abrego@csun.edu (Bernardo M. Ábrego), silvia.fernandez@csun.edu (Silvia
Fernández–Merchant), oaich@ist.tugraz.at (Oswin Aichholzer), jleanos@uaz.edu.mx (Jesús Leaños),
gsalazar@ifisica.uaslp.mx (Gelasio Salazar)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P2.10
1 Introduction
The rectilinear crossing number cr(G) of a graphG is the minimum number of edge cross-
ings in a rectilinear drawing of G in the plane, i.e., a drawing of G in the plane where the
vertices are points in general position and the edges are straight line segments. A drawing
of G with exactly cr(G) crossings is crossing-minimal.
Determining the rectilinear crossing number cr(Kn) of the complete graph Kn is a
well-known open problem in combinatorial geometry (see for instance [5, 11]). In [9]
Aichholzer et al. determined the exact values of cr(Kn) for 13 ≤ n ≤ 17. In that paper
also the following question was raised.
Question 1.1. Is it true that, for every integer n ≥ 4, there exists a crossing-minimal
drawing of Kn that contains a crossing-minimal drawing of Kn−1?
The exact value of cr(Kn) is known for n ≤ 27 and n = 30 (see [3, 7, 8, 9, 10]). The
value of cr(K18) = 1029 was established in [8]. Crossing-minimal rectilinear drawings of
Kn for this range of values of n can be found in [2] and [6]. In particular, from [6], we
know that there are at least 37269 non-isomorphic crossing-minimal drawings of K17.
Let θ denote the counterclockwise rotation of 2π/3 around the origin, and let
W := {(−51, 113), (6, 834), (16, 989), (18, 644), (18, 1068), (22, 211)}. From [2], we
know that the 18-point set W ∪ θ(W ) ∪ θ2(W ) induces a crossing-minimal drawing of
K18. See Figure 1 for an illustration of such a point set.
Our main result is the following.
Theorem 1.2. Up to order type isomorphism, there is a unique 18-point set whose induced
rectilinear drawing of K18 has cr(K18) crossings.
Let D be the (unique, in view of Theorem 1.2) crossing-minimal rectilinear drawing
of K18. It is easily verified that every subdrawing of D with 17 points has more than
cr(K17) = 798 crossings. This settles Question 1.1 in the negative.
In the next section, we introduce the necessary notation and additional concepts re-
quired for the proof of Theorem 1.2. In Section 4 we prove Theorem 1.2.
2 k-edges, (≤ k)-edges, and 3-decomposability
Throughout this section, Q is a set of n ≥ 3 points in general position in the plane. If p
and q are distinct points of Q, then we denote by pq the directed line spanned by p and q,
directed from p towards q. Furthermore, pq+ and pq− denote the set of points in Q on the
right and left, respectively, of pq. Thus Q = pq− ∪ {p, q} ∪ pq+ for all p, q ∈ Q with
p ̸= q.
Let k ∈ {0, 1, . . . , ⌊n/2⌋−1}. A k-edge ofQ is a directed line spanned by two distinct
points of Q, which leaves exactly k points of Q on one side. A (≤ k)-edge (respectively,
a (> k)-edge) is an i-edge of Q with 0 ≤ i ≤ k (respectively, k < i ≤ ⌊n/2⌋ − 1).
Let Ek(Q), E≤k(Q), and E>k(Q) denote, respectively, the set of k-edges, (≤ k)-edges
and (> k)-edges of Q. We use ek(Q), e≤k(Q), and e>k(Q) to denote, respectively, the
number of elements in Ek(Q), E≤k(Q), and E>k(Q). Then e≤k(Q) =
∑k
j=0 ej(Q) and
e>k(Q) =
(
n
2
)
− e≤k(Q).
The vector E≤k(Q) := (e≤0(Q), e≤1(Q), . . . , e≤⌊n/2⌋−1(Q)) is the (≤ k)-edges vec-
tor of Q. Finally, e≤k(n) denotes the minimum of e≤k(P ) taken over all n-point sets P
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 3
Figure 1: This is the 18-point set produced by the union of W = {(−51, 113), (6, 834),
(16, 989), (18, 644), (18, 1068), (22, 211)}, θ(W ) and θ2(W ). It is not difficult to see that
P produces a crossing-minimal rectilinear drawing ofK18. The triangle and the six straight
line segments show that P is 3-decomposable.
in the plane in general position. The exact determination of e≤k(n) is another well known
open problem in combinatorial geometry (see for instance [3, 4, 7, 8]).
The number of crossings in a rectilinear drawing of Kn and the number of k- and
(≤ k)-edges in its underlying n-point set P are closely related by the following equality,
independently proved in [4] and [12]:
cr(P ) =
⌊n/2⌋−2∑
k=0
(n− 2k − 3) e≤k (P )−
3
4
(
n
3
)
+
(
1 + (−1)n+1
) 1
8
(
n
2
)
. (2.1)
This equality allows us to fully determine the (≤ k)-edges vector of any 18-point set
whose induced drawing attains the rectilinear crossing number of K18.
Proposition 2.1. If P is an 18-point set such that cr(P ) = cr(K18), then E≤k(P ) =
(3, 9, 18, 30, 45, 63, 87, 120, 153).
Proof. Let Q be an 18-point set in the plane in general position. It is known (see [3]
or [7]) that E≤k(Q) = (e≤0(Q), e≤1(Q), . . . , e≤8(Q)) is bounded below entry-wise by
(3, 9, 18, 30, 45, 63, 87, 120, 153). On the other hand, from (2.1) we know that
cr(Q) = −612 + 15 · e≤0 (Q) + 13 · e≤1 (Q) + · · ·+ 1 · e≤7 (Q) .
From the coefficients of this equation and the fact that e≤8 (Q) = 153, it follows that if
e≤k (Q) is greater than the k-th component in the vector (3, 9, 18, 30, 45, 63, 87, 120, 153),
then cr(Q) > 1029.
4 Ars Math. Contemp. 24 (2024) #P2.10
Finally, we introduce a concept that captures a property shared by all known crossing-
minimal rectilinear drawings ofKn, for n a multiple of 3. A point setQ is 3-decomposable
if it can be partitioned into three equal-size sets A,B and C, such that (i) there exists a
triangle T enclosing the point set Q; and (ii) the orthogonal projection of Q onto the three
sides of T shows A between B and C on one side, B between C and A on the second
side, and C between A and B on the third side. In such a case, we say that {A,B,C}
is a 3-decomposition of Q. For instance, {W, θ(W ), θ2(W )} is a 3-decomposition of the
18-point set shown in Figure 1.
As in [2], if {A,B,C} is a 3-decomposition of Q, we define two types of edges. Let
p and q be distinct points of Q. If p, q ∈ A, p, q ∈ B or p, q ∈ C then we call pq
monochromatic; otherwise, pq is bichromatic. Let Emonk (Q) and E
bi
k(Q) denote the set of
monochromatic and bichromatic k-edges of Q, respectively. As before, we use emonk (Q) and
ebik(Q) to denote |Emonk (Q)| and |Ebik(Q)|, respectively. Note that ek(Q) = emonk (Q)+ ebik(Q).
Now we partition the monochromatic edges of Q into three types. If p, q ∈ A, then we
say that pq is an edge of type aa. Similarly, we define the edges of types bb and cc. For
x ∈ {a, b, c}, we denote the number of monochromatic k-edges of type xx by exxk (Q).
Then emonk (Q) = e
aa
k (Q) + e
bb
k (Q) + e
cc
k (Q).
3 Overview of the proof of Theorem 1.2
For the rest of this paper, P is an 18-point set in the plane in general position where the
rectilinear crossing number of K18 is attained. That is, cr(P ) = cr(K18).
The first step in the proof, carried out in Section 4.1, consists of giving an algo-
rithm that yields a canonical, unambiguous labelling of the points in P . The 18 points
in P get labelled x0, x1, . . . , x5, y0, y1, . . . , y5, z0, z1, . . . , z5. Thus P gets naturally par-
titioned into three sets X = {x0, x1, x2, x3, x4, x5}, Y = {y0, y1, y2, y3, y4, y5}, and
Z := {z0, z1, z2, z3, z4, z5}. As we shall prove shortly afterwards, {X,Y, Z} happens to
be a 3-decomposition of P .
Once we have laid out the foundation by giving a canonical labelling of the points of
P , the rest of the proof consists of showing the following:
Lemma 3.1 (Implies Theorem 1.2). For each pair of distinct points p, q ∈ P , the set pq+
is uniquely determined.
Clearly Lemma 3.1 implies Theorem 1.2: if the lemma holds, then the unambiguity of
the labelling of the points in P implies that P is unique up to order type isomorphism.
First we establish the lemma for the case in which pq is a (≤5)-edge. This is actually
done in Section 4.1, where we give the algorithm to label the points in P . Indeed, the
unambiguity in the labelling of the points in P is established in Proposition 4.3(1), and in
order to prove this we need to prove simultaneously Proposition 4.3(2), which in particular
implies Lemma 3.1 for the case in which pq is a (≤5)-edge.
We then move on to proving Lemma 3.1 for the case in which pq is a (>5)-edge, that is,
when pq is either a 6-edge, or a 7-edge, or an 8-edge. As we shall see, even if this follows
from elementary observations, the investigation of these cases is remarkably more involved
than the case in which pq is a (≤5)-edge.
The first step towards the investigation of (>5)-edges is given in Section 4.2, where we
prove that {X,Y, Z} is a 3-decomposition of P . This allows us to classify each edge of
P as either monochromatic or bichromatic, as we explained at the end of Section 2. Also
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 5
in Section 4.2 we show that for each k ∈ {6, 7, 8} it is easy to determine the number of
bichromatic k-edges and the number of monochromatic k-edges.
After proving these elementary properties of P we move on to Section 4.3. This is the
most technical and long part of the paper, and its purpose is to establish a collection of
structural properties of P . On a first read it may be advisable to skip this section, and only
come back to it whenever its main results are invoked in Sections 4.4 and 4.5.
Finally, in Section 4.4 (respectively, Section 4.5) we prove Lemma 3.1 for the case in
which pq is a monochromatic (respectively, bichromatic) 6-edge, 7-edge, or 8-edge. As we
shall see, using the structural results from Section 4.3 these tasks are reduced to a relatively
straightforward case analysis.
For completeness, the conclusion of the proof is presented in Section 4.6.
4 Proof of Theorem 1.2
We recall that throughout this paper, P is an 18-point set in the plane in general position
such that cr(P ) = cr(K18).
4.1 The algorithm to label the 18 points in P , and proof of Lemma 3.1 when pq is a
(≤ 5)-edge
It follows from Proposition 2.1 that the convex hull of P has exactly 3 vertices. Without
loss of generality (the whole set P may be rotated, if necessary) we may assume that all
three vertices have distinct x-coordinates. Let x0 denote the vertex with the smallest x-
coordinate. As we travel counterclockwise along the convex hull starting from x0, let y0
be the first vertex we find, and let z0 be the other vertex. See Figure 2.
Figure 2: The convex hull of P .
6 Ars Math. Contemp. 24 (2024) #P2.10
Observation 4.1. E0(P ) = {x0y0, y0z0, x0z0}. □
We have already unambiguously determined a labelling for the three convex hull ver-
tices of P . It remains to unambiguosly determine a labelling for the remaining 15 points of
P .
For j ∈ {0, . . . , 5}, let x↷j denote the j-th point in P that we find as we rotate the line
y0x0 clockwise around y0 (we consider x0 to be the 0-th point in P hit by the rotating line,
so that x↷0 = x0). We define y
↷
j and z
↷
j similarly, using z0y0 and x0z0 as the clockwise
rotating lines, around z0 and x0, respectively. See Figure 3(a).
In an analogous manner, we let x↶j denote the j-th point in P that we find as we rotate
the line z0x0 counterclockwise around z0 (again, we consider x0 to be the 0-th point in
P hit by the rotating line, so that x↶0 = x0). We define y
↶
j and z
↶
j similarly, using
x0y0 and y0z0 as the counterclockwise rotating lines, around x0 and y0, respectively. See
Figure 3(b).
Figure 3: (a) As we rotate the line y0x0 clockwise around y0, the third point in P we find
is labelled x↷3 . The points x
↷
1 and x
↷
2 are also indicated. (b) As we rotate the line z0x0
counterclockwise around z0, the third point in P we find is labelled x↶3 . The points x
↶
1 and
x↶2 are also indicated. By definition x
↷
0 = x
↶
0 = x0. Note that in this example x
↷
i = x
↶
i
for i = 0, 1, 2, 3.
Observation 4.2. For each j ∈ {0, . . . , 5}, y0x↷j , z0x↶j , z0y↷j , x0y↶j , x0z↷j , and y0z↶j
are all j-edges.
The next statement is our first major result on the structure of P . In particular, it yields
a labelling of all the points of P . As it happens, this proposition simultaneously establishes
Lemma 3.1 for the case in which pq is a (≤ 5)-edge.
Proposition 4.3. Let j ∈ {0, . . . , 5}. Then:
(1) For u ∈ {x, y, z}, u↷j and u↶j are the same point, which will be denoted uj;
(2) For all nonnegative integers m,n such that m+ n = j, we have that
(a) Ej(P ) = {umvn
∣∣m+n = j and uv ∈ {xy, yz, zx}}. Moreover, for such values
of m,n, and j the following holds:
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 7
(b) umv+n = {ui
∣∣ i < m} ∪ {vi∣∣ i < n} for any uv ∈ {xy, yz, zx}.
Proof. We prove (1) and (2) by induction on j. Since x↷0 = x
↶
0 = x0, y
↷
0 = y
↶
0 = y0,
and z↷0 = z
↶
0 = z0, it follows from Observations 4.1 and 4.2 that (1) and (2) are true for
j = 0. Now we let t ∈ {0, 1, 2, 3, 4} be an integer such that (1) and (2) hold for every j
such that 0 ≤ j ≤ t (in particular, the points xj , yj , zj are already defined for 0 ≤ j ≤ t).
We complete the proof by showing that then (1) and (2) hold for j = t+ 1.
Let Xt := {x0, . . . , xt}, Yt := {y0, . . . , yt}, Zt := {z0, . . . , zt}, and Pt := Xt ∪ Yt ∪
Zt. From the definitions involved, it follows that |Pt| = 3(t + 1). First we establish an
injection ψ : Pt → Et+1(P ).
Consider any point xi ∈ Xt. It follows from the induction hypothesis that xiyt−i is a
t-edge, and that xiy+t−i = {xr
∣∣ r < i} ∪ {yr ∣∣ r < t− i}.
Let xi be the first point that we find as we rotate the line xiyt−i counterclockwise
around xi. It is easy to see that the induction hypothesis implies that the rotating line hits
xi with its head, and so xix+i = {xr
∣∣ r < i}∪{yr ∣∣ r < t−i+1}. We define ψ(xi) = xixi.
In an analogous manner we define ψ(yi) and ψ(zi) for all yi ∈ Yt and zi ∈ Zt. Since ψ
defines a one-to-one relation and |Pt| = 3(t+ 1), it follows that |ψ(Pt)| = 3(t+ 1).
Let E′ := {x0z↷t+1, y0x↷t+1, z0y↷t+1}. Observation 4.2 implies that E′ ⊂ Et+1(P ).
We note that ψ(x0) = x0y↶t+1, ψ(y0) = y0z
↶
t+1, and ψ(z0) = z0x
↶
t+1. Using these
observations and that {x↷t+1, y↷t+1, z↷t+1} ∩ Pt = ∅, it follows that E′ ∩ ψ(Pt) = ∅. On the
other hand, from Proposition 2.1 it follows that |Et+1(P )| = 3(t + 2). Thus Et+1(P ) is
the disjoint union of ψ(Pt) and E′.
By way of contradiction, suppose that x↷t+1 ̸= x↶t+1. Then each point of {x1, . . . , xt}
is contained in the interior of the quadrilateral bounded by y0x↷t+1, z0x
↶
t+1, z0x0, and x0y0
(see Figure 4). From the induction hypothesis it follows that x↷t+1x
↶
t+1 /∈ E≤t(P ). This
and the fact that x↷t+1x
↶
t+1 /∈ ψ(Pt)∪E′ imply that |x↷t+1x↶t+1−| ≥ t+2. Then the interior
of the triangle T bounded by y0x↷t+1, z0x
↶
t+1, and x
↷
t+1x
↶
t+1 is nonempty, and, moreover,
it contains every element of Q := x↷t+1x
↶
t+1
− \ {x0, x1, . . . , xt}. Let p be the first point
of Q that z0x↶t+1 finds as it is rotated counterclockwise around x
↶
t+1. Then x
↶
t+1p must be
a (t + 1)-edge of P . On the other hand, it is immediately seen that x↶t+1p /∈ ψ(Pt) ∪ E′,
contradicting that Et+1 = ψ(Pt) ∪ E′.
This contradiction shows that x↷t+1 and x
↶
t+1 are the same point. Analogous arguments
show that y↷t+1 and y
↶
t+1 are the same point, and that z
↷
t+1 and z
↶
t+1 are the same point. This
proves (1) for j = t+ 1.
Now we show that (2) holds for j = t + 1. Note that at this point xt+1, yt+1, zt+1
are all well-defined. For each m ∈ {0, 1, . . . , t + 1}, we let Xm := {xi
∣∣ i ≤ m},
Ym := {yi
∣∣ i ≤ m}, and Zm := {zi ∣∣ i ≤ m}.
Let m ∈ {0, 1, 2, . . . , t+ 1}. We shall show that
(i) xmyt+1−m is in Et+1(P ); and
(ii) xmy+t+1−m = Xm−1 ∪ Yt−m.
By symmetry, analogous arguments show that: (i’) ymzt+1−m is in Et+1(P );
(ii’) ymz+t+1−m = Ym−1 ∪ Zt−m; (i”) zmxt+1−m is in Et+1(P ); and (ii”) zmx
+
t+1−m =
Zm−1 ∪ Xt−m. Note that these six assertions, together with the fact that |Et+1(P )| =
3(t+ 2), imply (2).
Thus we complete the proof by showing (i) and (ii).
8 Ars Math. Contemp. 24 (2024) #P2.10
Figure 4: If x↷t+1 ̸= x↶t+1, then the triangle T contains a point p such that x↶t+1p is a (t+1)-
edge of P .
Since xt+1 = x↶t+1 = x
↷
t+1, yt+1 = y
↶
t+1 = y
↷
t+1, and zt+1 = z
↶
t+1 = z
↷
t+1, it follows
that (i) and (ii) hold whenever m is in {0, t + 1}. Thus it suffices to prove (i) and (ii) for
1 ≤ m ≤ t.
From the induction hypothesis we have that xm−1y+t+1−m = Xm−2 ∪ Yt−m and
xmy
+
t−m = Xm−1 ∪ Yt−m−1. Also note that Xm−1 ∪ Yt−m ⊆ xmy+t+1−m.
LetB denote the triangle bounded by the lines xm−1yt+1−m, xmyt−m, and xmyt+1−m
(see Figure 5). Let PB be the set of points of P contained in the interior of B.
We claim that PB = ∅. By way of contradiction, suppose this is not the case. Let
L = p1p2 · · · pk be the lower chain of the convex hull of PB ∪ {xm, yt+1−m}. Then
p1 = xm and pk = yt+1−m, where (since B ̸= ∅) k ≥ 3. We note that pip+i+1 =
Xm−1 ∪Yt−m for all i = 1, 2, . . . , k− 1. Thus each edge of L is a (t+1)-edge. We recall
that Et+1(P ) = ψ(Pt)∪E′. It is readily seen that no edge of L is in E′, and so every edge
of L is in ψ(Pt). In particular, the line p2p3 is in ψ(Pt).
Recall that every edge in ψ(Pt) is obtained by starting with a line viwt−i (for v, w ∈
{x, y, z}, v ̸= w), counterclockwise rotating it around vi, and recording the first point
p in P hit by the rotating line: ψ(vi) is then the line vip. Thus, in particular p2p3 is
obtained in this way. Now if we reverse the process and clockwise rotate p2p3 around
p2, the first point hit by the rotating line must be yt−m. This implies that p2 = xm,
contradicting that p1 = xm. We therefore conclude that PB = ∅. Finally, note that
PB = ∅ immediately implies that ψ(xm) = xmyt+1−m. Thus xmyt+1−m is a (t + 1)-
edge. This proves (i). Moreover, as we observed above, Xm−1 ∪ Yt−m ⊆ xmy+t+1−m.
Since |Xm−1 ∪ Yt−m| = t+ 1, then Xm−1 ∪ Yt−m = xmy+t+1−m. Thus (ii) follows.
In view of Proposition 4.3(1), we have achieved our goal to unambiguously identify
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 9
Figure 5: If the interior of the triangle B is nonempty, then every edge of the convex chain
p1, p2, . . . , pk is a (t+ 1)-edge.
10 Ars Math. Contemp. 24 (2024) #P2.10
(and label) all 18 points of P . For the rest of the paper, we letX := {x0, x1, . . . , x5}, Y :=
{y0, y1, . . . , y5}, and Z := {z0, z1, . . . , z5}, where xj , yj , and zj are as in Proposition 4.3,
for j = 0, 1, . . . , 5.
4.2 {X,Y, Z} is a 3-decomposition of P
If we rotate the line x0z0 clockwise along x0, then for j = 1, 2, . . . , 5, the j-th point hit
by the rotating line is zj . If we rotate the line x0y0 counterclockwise along x0, then for
j = 1, 2, . . . , 5, the j-th point hit by the rotating line is yj . It follows that the sixth point hit
by the clockwise rotating line ℓx is in X , and the sixth point hit by the counterclockwise
rotation line ℓ′x is also in X (see Figure 6). These two points in X are obviously distinct
(since |X| > 2), and so they define an infinite cone CX with vertex x0 (here by cone with
vertex p we mean a pair of distinct directed rays, both with startpoint p). Note that CX is
the smallest infinite cone with vertex x0 that contains X . See Figure 6.
We similarly find infinite cones CY (with vertex y0) and CZ (with vertex z0).
Figure 6: The sets X,Y, and Z are contained in the indicated (closed) shaded regions. The
shaded region containing X is ∆X,Y ∩∆X,Z .
Now CX ∪ CY divide the plane into several regions, three of which are bounded. Two
of these bounded regions are triangles: one triangle ∆X,Y with x0 as a vertex and another
triangle ∆Y,X with y0 as a vertex; the other one is a quadrilateral. The entire set X is
contained in ∆X,Y , and the entire set Y is contained in ∆Y,X . By considering the pair
CX , CZ (respectively, CY , CZ), we obtain triangles ∆X,Z and ∆Z,X (respectively, ∆Y,Z
and ∆Z,Y ). Thus X ⊆ ∆X,Y ∩ ∆X,Z , Y ⊆ ∆Y,X ∩ ∆Y,Z , and Z ⊆ ∆Z,X ∩ ∆Z,Y .
Hence the situation is as illustrated in Figure 6. In this figure, each of ∆X,Y ∩ ∆X,Z ,
∆Y,X ∩∆Y,Z , and ∆Z,X ∩∆Z,Y is a quadrilateral, although it is easy to see that any (or
all) of them may be a triangle.
In view of this, it follows immediately that there is a triangle that witnesses the follow-
ing:
Proposition 4.4. P is 3-decomposable, with 3-decomposition {X,Y, Z}. □
As we mentioned in Section 2, knowing that {X,Y, Z} is a 3-decomposition of P
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 11
allows us to classify each edge of P as either monochromatic or bichromatic: for p, q ∈ P ,
the edge pq is monochromatic if p and q belong to the same set of the 3-decomposition
{X,Y, Z}. Otherwise, pq is bichromatic.
We close this section by noting that using the 3-decomposability of P it is easy to
determine the number of bichromatic and monochromatic k-edges in P , for each k ∈
{0, . . . , 8}.
Indeed, since P is 3-decomposable it follows from [2, Claim 1] that ebi≤k(P ) = 3
(
k+2
2
)
for k ∈ {0, . . . , 5}, ebi≤6(P ) = 81, and ebi≤7(P ) = 99. Also note that ebi≤8(P ) is the
total number of bichromatic edges of P , namely 3 · 6 · 6 = 108. Using that ebij(P ) =
ebi≤j(P )− ebi≤j−1(P ) for j ∈ {1, . . . , 8}, we obtain the following.
Proposition 4.5. ebik (P ) = 3(k + 1) for k ∈ {0, . . . , 5}, ebi6 (P ) = 18, ebi7 (P ) = 18, and
ebi8 (P ) = 9.
To obtain emon6 (P ), e
mon
7 (P ) and e
mon
8 (P ), we note that Proposition 2.1 implies that
e6(P ) = 24, e7(P ) = 33, and e8(P ) = 33. Since ej(P ) = ebij (P ) + e
mon
j (P ) for
j = 0, . . . , 8, Proposition 4.5 implies the following.
Corollary 4.6. emonk (P ) = 0 for k ∈ {0, . . . , 5}, emon6 (P ) = 6, emon7 (P ) = 15, and
emon8 (P ) = 24.
4.3 Structural properties of P
4.3.1 Determination of euuk (P ) for any u ∈ {x, y, z} and any k ∈ {0, . . . , 8}
Let u ∈ {x, y, z}, i ∈ {1, 2, . . . , 5}, and ℓu, ℓ′u be the directed rays forming the cone
CU with vertex u0 mentioned in the arguments leading to Proposition 4.4. See Figure 6.
From now on, we shall use ui0 to denote the i-th point of P that ℓu finds when it is rotated
clockwise around of u0 until it reaches ℓ′u. Clearly, {u10, u20, . . . , u50} = {u1, u2, . . . , u5}.
Our next observation is evident, but useful.
Observation 4.7. Let v1, v2, and v3 be three distinct points in P , and let ℓ := v1v2 and
ℓ′ := v1v3. Let P1 := ℓ− ∩ ℓ′+, P2 := ℓ+ ∩ ℓ′+, and P3 := ℓ− ∩ ℓ′−. Then P1, P2, and
P3 are pairwise disjoint subsets of P . See Figure 7. For i = 1, 2, 3, let ri be the number of
points in Pi. If P \ {v1, v2, v3} is the disjoint union of P1, P2, and P3, and pi is the i-th
point of P1 that ℓ finds when it is rotated counterclockwise around v1 until it reaches ℓ′,
then v1pi is a j-edge of P for j = min{r2 + i, 16− (r2 + i)}.
The next observation is immediate from the definition of ui0 and Observation 4.7.
Observation 4.8. Let u ∈ {x, y, z}. Then
(1) u0u10 and u0u
5
0 are both 6-edges,
(2) u0u20 and u0u
4
0 are 7-edges and they are the only 7-edges of the type u0u, and
(3) u0u30 is an 8-edge.
Claim 4 in [2] implies that euu8 (P ) ≤ 8 for each u ∈ {x, y, z}. Using this, together
with Observation 4.8 and Corollary 4.6, we obtain the following.
Proposition 4.9. Let u ∈ {x, y, z}. Then euuk (P ) = 0 for k ∈ {0, . . . , 5}, euu6 (P ) = 2,
euu7 (P ) = 5, and e
uu
8 (P ) = 8.
12 Ars Math. Contemp. 24 (2024) #P2.10
Figure 7: The i-th point of P1 := ℓ− ∩ ℓ′+ that ℓ finds when it is rotated counterclockwise
around v1 is a j-edge for j = min{r2 + i, 16− (r2 + i)}, where r2 denotes the number of
points of P2 := ℓ+ ∩ ℓ′+.
The next corollary follows immediately from Observation 4.8(1) and Proposition 4.9.
Corollary 4.10. Emon6 (P ) = {x0x10, x0x50, y0y10 , y0y50 , z0z10 , z0z50}. Moreover, any other
monochromatic edge must belong to Emon7 (P ) ∪ Emon8 (P ).
4.3.2 Determination of the convex hull of U for U ∈ {X,Y, Z} and related facts
Let u be any element of {x, y, z}. One of the main goals in this subsection is to show
that the triangle formed by u0, u4 and u5 contains in its interior the remaining u’s, namely,
u1, u2 and u3. We also prove other statements about the relative position of the elements
of U . Almost all these assertions will be used in the subsequent steps later on.
Proposition 4.11. Let u ∈ {x, y, z}. If u1 ∈ {u20, u40}, then there are at least three 7-edges
of type uu involving u1 but not u0.
Proof. We prove the proposition for the case u = x. The cases u = y and u = z are
handled in a totally analogous manner.
Suppose that x1 = x40. Then ℓ := x0x1 leaves x
1
0, x
2
0 and x
3
0 on its left halfplane
(and x50 on its right halfplane). Let z
′ be the first z that ℓ finds when it is rotated counter-
clockwise around x1, and let ℓ′ = x1z′. See Figure 8. By Corollary 4.10, we know that
{x1x10, x1x20, x1x30} ⊂ Emon7 (P ) ∪ Emon8 (P ). Then ℓ finds each of x10, x20 and x30 before
it reaches z′. This and Observation 4.7 imply that at most one of x1x10, x1x
2
0, x1x
3
0 is an
8-edge and, by Corollary 4.10, the other two must be 7-edges.
From the way in that the x′s were labelled it follows that x50 is the first x that ℓ finds
when it is rotated clockwise around x1, and so x1x50 is a (≤ 7)-edge. This and Corol-
lary 4.10 imply that x1x50 is the third required 7-edge. The case x1 = x
2
0 can be handled in
an analogous manner (y′s play the role of z’s).
Proposition 4.12. Let u ∈ {x, y, z} and {p, q} = {x, y, z} \ {u}. Suppose that
{q0, . . . , q5} ⊂ u0u3−0 and that {p0, . . . , p5} ⊂ u0u
3+
0 . Then:
(A1) u1 /∈ {u10, u50};
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 13
Figure 8: Here x0x1 is a 7-edge.
(A2) there are at least two 7-edges of type uu involving u1 but not u0;
(A3) u2 /∈ {u10, u50};
(A4) each of u3u4, u3u5 and u4u5 is an 8-edge;
(A5) {u10, u50} = {u4, u5};
(A6) the triangle formed by u0, u4 and u5 is the convex hull of U ; and
(A7) if u5 ∈ u0u+4 , then u0u
−
4 = {q0, . . . , q5} and u0u
+
5 = {p0, . . . , p5}. Otherwise,
u0u
+
4 = {p0, . . . , p5} and u0u
−
5 = {q0, . . . , q5} .
Proof. By rotating P if necessary, and exchanging appropriately the labels x, y, and z, we
can assume, without any loss of generality, that u = x, p = y, q = z and that X,Y and Z
are placed as in Figure 9.
(A1): Seeking a contradiction, suppose that x10 = x1. Let v be the first point that x0x1
finds when it is rotated clockwise around x1 as shown in Figure 9(a). Note that v ∈ Y ,
as otherwise v ∈ {x2, x3, x4, x5} and x1v− = Z. Then x1v is a 6-edge, contradicting
Corollary 4.10. Let x′ be the last element of {x2, x3, x4, x5} that x1v finds when it is
rotated clockwise around x1. Since v ∈ Y , then x1x′ must be a (≤ 6)-edge, contradicting
Proposition 4.9. The case x50 = x1 can be handled in an analogous manner (with the roles
of Z and Y interchanged).
(A2): From (A1) we know that x0x1 leaves at least one x in each side. By definition
of x1, the points x2, x3, x4 and x5 must be contained in X ′ := X ∩ x1z+0 ∩ x1y
−
0 , see
Figure 9(b). Let x′ be the last element of {x2, x3, x4, x5} that x0x1 finds when it is rotated
clockwise around x1 as shown in Figure 9(b). Note that x1x′ must be a (≤ 7)-edge. Since
x′ ̸= x0, then Proposition 4.9 implies that x1x′ must be a 7-edge. Similarly, if we rotate
x0x1 in the other direction, then we can find the other 7-edge involving x1 but not x0.
(A3): Seeking a contradiction, suppose that x2 = x10. Then x0x2 is a 6-edge, and
x3, x4 and x5 are contained in X ′′ := X ∩x10y−0 . See Figure 10(b). From Observation 4.7,
we know that at most one of x2x3, x2x4, x2x5 is an 8-edge. This and Corollary 4.10 imply
14 Ars Math. Contemp. 24 (2024) #P2.10
Figure 9: (a) x0x1 cannot be a 6-edge. (b) There are at least two 7-edges of type xx
involving x1 but not x0.
that at least two of x2x3, x2x4, x2x5 are 7-edges. This together with Observation 4.8(2)
and (A2) imply that exx7 (P ) ≥ 6, which contradicts Proposition 4.9. The case x2 = x50 can
be handled in an analogous manner.
(A4): From Corollary 4.10, Observation 4.8(1), and (A1), we know that x0x1 is a 7-
edge or an 8-edge. First suppose that x0x1 is a 7-edge. Then x1 ∈ {x20, x40}. This together
with Propositions 4.9 and 4.11 and Observation 4.8(2) imply that each element of Exx7 (P )
contains at least one of x0 or x1. This fact and Proposition 4.9 imply that x3x4, x3x5 and
x4x5 are 8-edges, as required.
Now, we suppose that x0x1 is an 8-edge. Then x2 ∈ x0x−1 or x2 ∈ x0x
+
1 . We
only analyze the case x2 ∈ x0x−1 (the other case is symmetric). Then we must have
that X ′ := X ∩ x0x+1 ∩ x2y
−
0 contains exactly two elements x
′, x′′ of {x3, x4, x5}, see
Figure 10(a). Now we rotate x2y0 clockwise around x2 until it be parallel to x0x1. See
Figure 10(a). From Observation 4.7 and Corollary 4.10, we know that at least one of
x2x
′, x2x
′′ is a 7-edge. Such a 7-edge plus the four 7-edges provided by Observation 4.8(2)
and (A2) give us, 5, the total number of 7-edges of P . This and Proposition 4.9 imply that
x3x4, x3x5, x4x5 are 8-edges, as required.
(A5): Seeking a contradiction, suppose that {x10, x50} ̸= {x4, x5}. Then (A1) and (A3)
imply that x3 = x10 or x3 = x
5
0. Again, by symmetry it is enough to analyze the case
x3 = x
1
0. Clearly, both x1 and x2 are contained in the triangle formed by x0x3, x0x
5
0 and
x3y0; and x4, x5 are contained in X ′′ := X ∩ x10y−0 , see Figure 10(b).
Now we rotate x0x3 clockwise around x3 until it reaches x3y0, and note that such a
rotation hits x4 and x5. From Observation 4.7 we know that at most one of x3x4 or x3x5
is 8-edge, contradicting (A4).
(A6): This follow directly from (A5) and the way in that the x’s were labelled.
(A7): Suppose that x5 ∈ x0x+4 . Then (A5) implies that x10 = x4 and x50 = x5. The
required equalities follow from the definition of x10 and x
5
0 and the hypotheses Z ⊂ x0x3−0
and Y ⊂ x0x3+0 . Similarly, we can deduce that x0x
−
5 = Z and x0x
+
4 = Y whenever
x5 ∈ x0x−4 .
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 15
Figure 10: (a) x3x4, x3x5, x4x5 are 8-edges. The dotted straight line containing x2 is
parellel to x0x1. (b) {x10, x50} = {x4, x5}, and hence x0x4 and x0x5 are 6-edges.
4.3.3 Determination of the position of u5 with respect to u0u4 for each u ∈{x, y, z}
Our main goal in this subsection is to show that u5 ∈ u0u+4 for each u ∈ {x, y, z}. In order
to prove this, we need to establish some auxiliary statements that will also be used later on.
Let u, v ∈ {x, y, z} with u ̸= v. We will say that u4u5 splits the v’s to mean that u4u5
separates {u0, . . . , u3} ∪ {v0, . . . , v3} from the rest of the points of P \ {u4, u5}.
Proposition 4.13. Let {u, v, w} = {x, y, z}, and suppose that u0u5 separates u4 from the
v’s. Then u4u5 splits the v’s.
Proof. By rotating and/or reflecting P along u0u4, if necessary, we can assume that u =
x, v = y, w = z and that X,Y and Z are placed as in Figure 6.
Since x0x5 separates x4 from the y’s, then x5 ∈ x0x+4 . From Proposition 4.3 we know
that x4y+0 = {x0, x1, x2, x3}. Then (A6) implies that x4y
+
0 ⊆ x4x
+
5 . If we rotate x4y0
counterclockwise around x4 until it reaches x0x4, then x5 ∈ x0x+4 , (A6), and Observa-
tion 4.7 together imply that at most one element of {x4x5} ∪ {x4y
∣∣y ∈ Y } is an 8-edge.
This and (A4) imply that such an 8-edge must be x4x5. Then (A6) implies that x4x5 leaves
exactly four y’s on its right. Moreover, from Proposition 4.3 it is easy to see that y0 and y1
are in x4x+5 . Let yi and yj be two elements of Y in x4x
−
5 . Without loss of generality, we
can assume that i < j. Then 2 ≤ i < j ≤ 5.
From (A6) we know that the triangle formed by y0, y4, and y5 is the convex hull of Y .
This implies that j ∈ {4, 5}. Seeking a contradiction, suppose that i ∈ {2, 3}.
Let T be the triangle formed by x0x5, x0yi and x4x5. See Figure 11(b). By the way y’s
were labelled, we know that if yr ∈ T then r ∈ {i+1, . . . , 5}\{j}. Let y′ be the first point
in Y ∩ T that yix0 finds when it is rotated clockwise around yi. See Figure 11(b). Then
yiy
′ is a (≤ i + 4)-edge because the points of P lying in the left side of yiy′ is a subset
of {x0, . . . , x3, y0, . . . , yi−1}. If i = 2, then yiy′ is a (≤ 6)-edge which does not involve
y0, contradicting Corollary 4.10. Finally, if i = 3, then yiy′ is a (≤ 7)-edge, contradicting
(A4).
Observation 4.14. From Proposition 4.13 we know that if {u, v, w} = {x, y, z}, then
u4u5 splits the v’s or the w’s.
16 Ars Math. Contemp. 24 (2024) #P2.10
Figure 11: (a) If x4 ∈ x0x−5 , then x4x5 splits Y . (b) There are exactly two y’s, namely yi
and yj , in x4x−5 .
Proposition 4.15. Let u and v be two distinct elements of {x, y, z}. If u4u5 splits the v’s,
and v3v5 leaves u0 and v2 on the same side, then v4v5 splits the u’s.
Proof. By rotating P if necessary and exchanging appropriately the labels x, y and z, we
can assume that u = x and that X,Y and Z are placed as in Figure 6.
CASE 1: Suppose that x4x5 splits the y’s. Then we need to show that if y3y5 leaves x0
and y2 on the same side, then y4y5 splits the x’s.
From (A4), we know that y4y5 is an 8-edge, and from (A6), that y4y5 is in the convex
hull of Y .
First, we show that y5 ∈ y0y−4 . By way of contradiction, suppose this is not the case.
Then y5 ∈ y0y+4 and the triangle formed by y0, y4 and y5 looks like in Figure 12(a). Since
x4x5 splits the y’s, then x4x5 separates y3 from y4 and y5, and so all the x’s are on the
left side of both y3y4 and y3y5. In particular, x0 ∈ y3y−5 , and hence y2 ∈ y3y
−
5 . Then
y2 ∈ y3y−5 ∩ z0y
−
3 , and so y2 is contained in the triangle Q formed by y0y4, z0y3, y3y5.
See Figure 12(b). Since y3y4 is an 8-edge by (A4), and y3y4 leaves {y0, y2, x0, . . . , x5}
on its left, then it leaves y1, y5 on its right. This and the fact that y1 ∈ z0y−3 imply that
y1 is contained in the triangle R formed by z0y3, y3y4, y0y5. See Figure 12(b). Then y2y4
and y0y1 are 7-edges. This, together with Observation 4.8(2) and Proposition 4.11, implies
eyy7 (P ) ≥ 6, the required contradiction. Thus, we can conclude that y0y4 leaves the x’s
and y5 on the same side, and the desired result follows from Proposition 4.13.
CASE 2: x4x5 splits the z’s. Follow the same argument as in CASE 1 with left, right,
y, z,− and + in place of right, left, z, y,+ and −, respectively.
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 17
Figure 12: (a) y5 ∈ y0y+4 . (b) y2 is in Q and y1 is in R.
Proposition 4.16. If u ∈ {x, y, z}, then u3u5 leaves u0 and u1 on the same side.
Proof. As in Proposition 4.15, we can assume that u = x and thatX,Y andZ are placed as
in Figure 6. From (A4), we know that x3x5 is an 8-edge. Seeking a contradiction, suppose
that x3x5 separates x0 from x1.
First, suppose that x4x5 splits the y’s. Since P is placed as in Figure 6, then x0 ∈ x3x+5 ,
and hence, x1 ∈ x3x−5 . Then x3x
+
5 = {x0, x2}∪Y , or equivalently, x3x
−
5 = {x1, x4}∪Z.
This fact has two immediate consequences. The first one is that x1 = x20. This fact and
Proposition 4.11 imply that there are at least three 7-edges of type xx involving x1 but
not x0. The second consequence is that x2 is in the triangle X ′ (see Figure 13) formed
by x1y0, x3x5 and x0x5, and hence x2x5 must be a 7-edge too. The existence of these
four 7-edges together with those in Observation 4.8(2) imply exx7 (P ) ≥ 6, contradicting
Proposition 4.9.
Now suppose that x4x5 splits the z’s. Again, since P is placed as in Figure 6, then x0 ∈
x3x
−
5 and x1 ∈ x3x
+
5 . By similar arguments as above, we can deduce that x1 = x
4
0 and that
x2x5 is a 7-edge. As before, x1 = x40 and Proposition 4.11 imply that there are at least three
7-edges of type xx involving x1 but not x0. The existence of these four 7-edges together
with those in Observation 4.8(2) imply exx7 (P ) ≥ 6, contradicting Proposition 4.9.
Proposition 4.17. There is a u ∈ {x, y, z} such that u3u5 separates u4 from the other u’s.
Proof. From Proposition 4.16 we know that u3u5 leaves u0 and u1 on the same side for
each u ∈ {x, y, z}. Seeking a contradiction, we suppose that u3u5 separates {u0, u1} from
{u2, u4} for each u ∈ {x, y, z}.
By rotating and/or reflecting P if necessary, and exchanging appropriately the labels
x, y and z, we can assume that X,Y and Z are placed as in Figure 11(a), and that x4x5
splits the y’s. An immediate consequence of these assumptions and our hypothesis is that
(i) x3x5 leaves to z0 and x2 on its left side.
18 Ars Math. Contemp. 24 (2024) #P2.10
Figure 13: Here x1 ∈ x3x−5 .
Now suppose that y5 ∈ y0y+4 . Then y0y5 separates y4 from the z’s, and from Proposi-
tion 4.13 we know that y4y5 splits the z’s. In particular, the triangle formed by y0, y4 and
y5 must be as in Figure 12(a) and y0 ∈ y3y+5 . By supposition, y3y5 separates y0 from y2,
and so y3y5 leaves to x0 and y2 on its left side. This last and Proposition 4.15 imply that
y4y5 splits the x’s too, which is impossible. Thus we conclude that y5 ∈ y0y−4 . This and
Proposition 4.13 imply that y4y5 splits the x’s. This fact and our supposition imply that (ii)
y3y5 leaves to z0 and y2 on its right side.
If z4z5 splits the x’s, then (i) and Proposition 4.15 imply that x4x5 splits the z’s, which
contradicts that x4x5 splits the y’s. Similarly, if z4z5 splits the y’s, then (ii) and Proposi-
tion 4.15 imply that y4y5 splits the z’s, again contradicting that y4y5 splits the x’s.
Proposition 4.18. Let u be an element in {x, y, z} that satisfies the property in Propo-
sition 4.17, and suppose that u4u5 splits the v’s, where v ∈ {x, y, z} \ {u}. Then the
following hold:
(B1) u3u5 separates v5 from the other v’s;
(B2) v4v5 splits the w’s, where {w} = {x, y, z} \ {u, v};
(B3) v1v4 and v2v4 are both 7-edges; and
(B4) v3v5 separates v4 from the other v’s.
Proof. Without loss of generality, we can assume that u = x, v = y, and X,Y and Z are
placed according to Figure 11. Indeed, we can get such requirements by rotating and/or
reflecting P , and by exchanging appropriately the labels x, y and z.
(B1): From our assumptions and the hypothesis we know that x4 is the only x in x3x−5 .
Since x3x5 is an 8-edge, then exactly one element y∗ of Y is in x3x−5 . From (A6), we know
that such a y∗ is one of y4 or y5. If y∗ = y4, then, by the way y0, . . . , y5 were labelled, we
have that y5 must be contained in the triangle S of Figure 14. Then y4y5 leaves x3, x4, x5
and all the z’s on its right side. This implies that y4y5 cannot be an 8-edge, contradicting
(A4). This contradiction implies that (B1) holds.
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 19
(B2): From (B1), we know that y∗ = y5 is the only element of Y in x3x−5 . If y5 ∈
y0y
−
4 , then y4 must be contained in the region R of Figure 14. This implies that each
element in (X ∪ Y ) \ {x4, y4, y5} lies in y4y−5 , contradicting (A4) that y4y∗ = y4y5 is
an 8-edge. Thus we have that y5 ∈ y0y+4 . This fact and Proposition 4.13 imply that y4y5
splits the z’s, as required.
In view of (B2) and our previous assumptions, for the rest of the proof, we may assume
that the two triangles defined by {x0, x4, x5} and {y0, y4, y5} are as shown in Figure 12(a).
(B3): Let ℓ be the line through y4 which is parallel to x4x5 and let M be the interior of
the triangle formed by y0y5, y0y4 and x4x5. See Figure 12(a). Since y4 and y5 are the only
y’s in x4x−5 , then M ∩ Y = {y1, y2, y3}. If we rotate ℓ in clockwise order around y4 until
it reaches y4y0, then by Observation 4.7 we have that exactly one of {y1y4, y2y4, y3y4} is
8-edge and the other two are 7-edges. The desired assertion follows from (A4).
(B4): Seeking a contradiction, suppose that y3y5 does not separate y4 from the other
y’s. Then Proposition 4.16 implies that y3y5 separates {y0, y1} from {y2, y4}. On the other
hand, since y3y4 is an 8-edge and x4x5 separates y3 from y4, then y3y−4 = X ∪ {y0, y2}.
Thus y1 must be contained in the triangle R formed by z0y3, y3y4, y0y5. See Figure 12(b).
This implies that y40 = y1. Then Proposition 4.11, Observation 4.8(2) and (B3) imply,
eyy7 (P ) ≥ 6, a contradiction.
Figure 14: Here x3x5 separates y∗ from the other y’s.
Remark 4.19. From now on, without loss of generality, we assume that the u ∈ {x, y, z}
satisfying Proposition 4.17 is x, and that x5 ∈ x0x+4 . Indeed, it is not hard to see that we
can get such requirements by rotating and/or reflecting P along x0x4, and by appropriately
exchanging the labels x, y and z. In particular, we assume that X,Y, Z, x0, x4 and x5 are
placed as in Figure 11.
Note that (B4) appears as hypothesis in Propositions 4.17 and 4.18. The following
corollary is an immediate consequence of this fact.
Corollary 4.20. Let σ(x) = y, σ(y) = z and σ(z) = x. The following hold for each
u ∈ {x, y, z}:
(C1) u3u5 separates σ(u)5 from the other σ(u)’s;
(C2) σ(u)4σ(u)5 splits the σ(σ(u))’s;
20 Ars Math. Contemp. 24 (2024) #P2.10
(C3) σ(u)1σ(u)4 and σ(u)2σ(u)4 are both 7-edges;
(C4) σ(u)3σ(u)5 separates σ(u)4 from the other σ(u)’s; and
(C5) u5 ∈ u0u+4 .
Proof. In view of Remark 4.19, we may assume that x4x5 splits the y’s, x3x5 separates x4
from the other x’s, and X,Y, Z, x0, x4 and x5 are placed as in Figure 11.
First, we show that (C1) – (C4) hold. Proposition 4.18 states exactly (C1) – (C4) for
u = x and v = σ(x) = y. In particular, (C2) and (C4) tell us that y4y5 splits the z’s and
that y3y5 separates y4 from the other y’s, respectively. By applying Proposition 4.18 to the
last two conclusions on y’s we have that (C1) – (C4) also hold for u = y and v = σ(y) = z.
Similarly, we can conclude that (C1) – (C4) also hold for u = z and v = σ(z) = x.
Now, we show (C5). For u = x the assertion holds by Remark 4.19. We first analyze
the case u = y. From (A6) and Remark 4.19, we know that {x0, . . . , x5} lies on the left
side of both y0y4 and y0y5. Seeking a contradiction, suppose that y5 ∈ y0y−4 . Then, from
(A6) and the last two facts, it is easy to verify that x0 ∈ y3y−5 . Similarly, from y5 ∈ y0y
−
4
and (C4), we can deduce that y2 ∈ y3y−5 . Thus x0, y2 ∈ y3y
−
5 , and so Proposition 4.15
implies that y4y5 splits the x’s, contradicting (C2). An analogous argument shows that (C5)
also holds for u = z.
From Remark 4.19 and Corollary 4.20, we have that the points of P with indices 0, 3, 4
and 5 are placed as in Figure 15.
Figure 15: The relative position of the points of P with indices 0, 3, 4 and 5.
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 21
4.4 Determination of pq+ when pq is a monochromatic edge.
Lemma 3.1 for the case in which pq is a monochromatic edge will follow from Proposi-
tions 4.21 and 4.22 below. Regarding the statements of these propositions, we recall from
Remark 4.19 and Corollary 4.20 that x4x5 splits the ys, y4y5 splits the zs, and z4z5 splits
the xs.
Proposition 4.21. Let u ∈ {x, y, z}, and let v be the element in {x, y, z} \ {u} such that
u4u5 splits the vs. Then the following hold:
(D1) u0u+5 = {v0, . . . , v5};
(D2) u0u+4 = {u1, u2, u3, u5} ∪ {v0, . . . , v5};
(D3) u4u+5 = {u0, u1, u2, u3} ∪ {v0, v1, v2, v3}; and
(D4) u3u+5 = {u0, u1, u2} ∪ {v0, v1, v2, v3, v4}.
Proof. (D1): From (A7), we know that u0u5 separates the v’s from the w’s. Moreover,
because u0u5 is an edge of the convex hull of U , then u0u5 leaves the other u’s on the
same side. This and (C5) imply that {u1, u2, u3, u4} ⊂ u0u−5 . Again, from (C5) and
Proposition 4.13 we have that {v0, v1, v2, v3} ⊂ u4u+5 , and hence {v0, v1, v2, v3} ⊂ u0u
+
5 .
This and the fact that u0u5 separates the v’s from the w’s imply that {v0, . . . , v5} ⊆ u0u+5 .
We finally note that Observation 4.8(1) implies that u0u+5 = {v0, . . . , v5}, as required.
(D2): From (C5), (D1), and the way in that the points of P were labelled we have
that {v0, . . . , v5} = u0u+5 ⊂ u0u
+
4 . On the other hand, since u0u4 is an edge of the
convex hull of U , then u0u4 leaves the other u’s on the same side. This and (C5) imply
that {u1, u2, u3, u5} ⊂ u0u+4 . Thus {u1, u2, u3, u5} ∪ {v0, . . . , v5} ⊂ u0u
+
4 . Again,
Observation 4.8(1) implies that u0u+4 = {u1, u2, u3, u5} ∪ {v0, . . . , v5}, as required.
(D3): It follows immediately from (C5) and Proposition 4.13.
(D4): Clearly, {v0, . . . , v5} ∩ u4u+5 ⊂ {v0, . . . , v5} ∩ u3u
+
5 . This fact, together
with (C1) and (D3), implies that {v0, v1, v2, v3, v4} ⊂ u3u+5 . On the other hand, from
(C4) is easy to verify that {u0, . . . , u5} ∩ u3u+5 = {u0, u1, u2}. Then {u0, u1, u2} ∪
{v0, v1, v2, v3, v4} ⊂ u3u+5 . We finally note that (A4) implies that u3u
+
5 = {u0, u1, u2} ∪
{v0, v1, v2, v3, v4}, as required.
Proposition 4.22. Let u ∈ {x, y, z}, and let v be the element in {x, y, z} \ {u} such that
u4u5 splits the vs. Then the following hold:
(E1) u0u1 is an 8-edge;
(E2) u0u2 and u0u3 are 7-edges;
(E3) u2u3 and u2u5 are 8-edges;
(E4) u2u+4 = {u5} ∪ {v0, . . . , v5};
(E5) u1u+4 = {u2, u3, u5} ∪ {v0, . . . , v5} and u3u
+
4 = {u2, u5} ∪ {v0, . . . , v5};
(E6) u0u+2 = {u5} ∪ {v0, . . . , v5};
(E7) u0u+1 = {u2, u5} ∪ {v0, . . . , v5} and u0u
+
3 = {u1, u2, u5} ∪ {v0, . . . , v5};
22 Ars Math. Contemp. 24 (2024) #P2.10
(E8) u1u+5 = {u0} ∪ {v0, . . . , v5};
(E9) u1u2 and u1u3 are 8-edges;
(E10) u1u+3 = {u2, u5} ∪ {v0, . . . , v5};
(E11) u1u+2 = {u0, u5} ∪ {v0, . . . , v5};
(E12) u2u+5 = {u0, u1} ∪ {v0, . . . , v5}; and
(E13) u2u+3 = {u4, u5} ∪ {v0, . . . , v5}.
Proof. (E1): From Proposition 4.9, Corollary 4.10, and (A5), we know that x0x1 is a 7- or
an 8-edge. If x0x1 is a 7-edge, then x1 ∈ {x20, x40} and by Proposition 4.11, there are at
least three 7-edges of type xx involving x1 but not x0. This, Observation 4.8(2), and (C3)
imply that exx7 (P ) ≥ 6, a contradiction. Thus x0x1 must be an 8-edge.
(E2): From Observation 4.8(2), we know that there are exactly two 7-edges of the type
x0x. Since (E1) and (A6) imply that none of x0x1, x0x4, x0x5 is a 7-edge, then both x0x2
and x0x3 are 7-edges, as desired.
(E3): By Corollary 4.10 and (A5), each of x2x3 and x2x5 is a 7- or an 8-edge. From
(C3) and (E2), we know that each of x1x4, x2x4, x0x2, x0x3 is a 7-edge. Since (A2) guar-
antees the existence of an additional 7-edge involving x1 and exx7 (P ) = 5, then x2x3 and
x2x5 are 8-edges, as required.
Observation 4.23. Since z4z5 separates {x4, x5} from the other x’s (see Figure 15), then
xix4 leaves Z on its left for any i ∈ {0, 1, 2, 3}.
(E4): From (C3), we know that x1x4 and x2x4 are 7-edges. This and Observation 4.23
imply that x2x4 leaves exactly 1 or exactly 3 points of X on its left.
Suppose first that x1 ∈ x2x+4 . Since x0 ∈ x2x
−
4 , then x2x
+
4 = {x1, x3, x5} ∪ Y .
Again, Observation 4.23 implies that when we rotate x2x4 counterclockwise around x4,
the first two points that such line finds (with the tail) are x1 and x3. Since x1x4 is a 7-edge
and x3x4 is an 8-edge, then the first point that such a rotation finds must be x3, and hence
x1 ∈ x3x+4 . This and the way in which the x′s were labelled imply that x40 = x1. But then
x0x1 is a 7-edge, contradicting (E1). Then x0, x1 ∈ x2x−4 and hence x2x4 leaves exactly
three points of X on its left, namely x0, x1 and x3. The desired equality follows from the
last conclusion, Observation 4.23, and (C3).
(E5): From (A4), we know that x3x4 is an 8-edge, and from (C3) that x1x4 is a 7-edge.
Since x1, x3 ∈ x2x−4 , by (E4), then when we rotate x2x4 clockwise around x4, the first two
points that such line finds (with the tail) are precisely x1 and x3. Since x1x4 is a 7-edge and
x3x4 is an 8-edge, then such a rotation finds first x3 and then x1. The desired conclusions
are immediate from this fact and (E4).
(E6): From (E4) and the way the x’s were labelled, we know that when we rotate x2x4
clockwise around x2, the first point that such line finds (with the tail) is one of x0 or x1.
Since x0x2 is a 7-edge, by (E2), then such a point must be x0 and the desired result follows
from (E4).
(E7): From (E6), we know that the first two points that we find when we rotate x0x2
counterclockwise around x0 are x1 and x3. Since x0x1 is an 8-edge, by (E1), then we
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 23
have that such a rotation finds x1 and then x3. These together with (E6) imply the desired
results.
(E8): (D4) implies that x3 ∈ x1x−5 . If x2 ∈ x1x
+
5 , then {x1, x3, x4} ∪ Z ⊂ x2x
−
5 .
This would imply that x2x5 is not an 8-edge, contradicting (E3). Then we can assume that
x2 ∈ x1x−5 . Thus, x0 is the only x on the right side of x1x5 and hence x1x5 is a (≤ 7)-
edge. From Proposition 4.9 and Corollary 4.10, we have that x1x5 must be a 7-edge. This
implies that Y ⊂ x1x+5 , and hence (E8) holds.
(E9): (E4), (E5), (E6), (E7), and (E8) imply, respectively, that x2x4, x1x4, x0x2, x0x3
and x1x5 are 7-edges. Then Proposition 4.9 implies that these five are all the monochro-
matic edges of type xx. This and Corollary 4.10 imply that x1x2 and x1x3 must be 8-edges.
(E10): The first assertion of (E7) implies that x3, x4 ∈ x0x−1 and x2, x5 ∈ x0x
+
1 .
From the first assertion of (E5) we know that x2, x3 ∈ x1x+5 . Then when we rotate x0x1
counterclockwise around x1, the first point that such line finds must be x3, and so the
desired result follows immediately from this and the first assertion of (E5).
(E11): From the first assertion of (E7), we have that x3, x4 ∈ x0x−1 and x2, x5 ∈ x0x
+
1 .
From (E8), we know that x2, x3 ∈ x1x−4 . Then when we rotate x0x1 clockwise around x1,
the first point that we find is x2, and so the desired result follows from the first assertion of
(E7).
(E12): (E8) implies {x2, x3, x4} ∪ Z = x1x−5 . From (D4) and the second assertion of
(E3), we know that when we rotate x1x5 clockwise around x5, the first point that we find
must be x2, and so the desired result follows from (E8).
(E13): (E4) implies that Z ∪ {x0, x1, x3} = x2x−4 . From (E10), we know that x2 ∈
x1x
+
3 . This and the first assertion of (E3) imply that when we rotate x2x4 counterclockwise
around x2, the first point that we find must be x3, and so the desired result follows from
(E4).
4.5 Determination of pq+ when pq is a bichromatic (>5)-edge.
We are finally ready to prove Lemma 3.1 for the remaining case, namely when pq is a
bichromatic (> 5)-edge. This is achieved in the next statement. We recall from Re-
mark 4.19 and Corollary 4.20 that x4x5 splits the ys, y4y5 splits the zs, and z4z5 splits
the xs.
Proposition 4.24. Let u ∈ {x, y, z}, and let v be the element in {x, y, z} \ {u} such that
u4u5 splits the vs. Then the following hold:
(F1) u5v+4 = {u0, u1, u2, u3} ∪ {v0, v1, v2, v3};
(F2) u5v+5 = {u0, u1, u2} ∪ {v0, v1, v2, v3, v4};
(F3) u5v+3 = {u0, u1, u2, u3, u4} ∪ {v0, v1, v2};
(F4) u5v+2 = {u0, u1, u2, u3, u4} ∪ {v0, v1};
(F5) u5v+1 = {u0, u1, u2, u3, u4} ∪ {v0};
(F6) u4v+4 = {u0, u1, u2, u3, u5} ∪ {v0, v1, v2, v3};
(F7) u4v+5 = {u0, u1, u2, u3, u5} ∪ {v0, v1, v2, v3, v4};
24 Ars Math. Contemp. 24 (2024) #P2.10
(F8) u4v+3 = {u0, u1, u2, u3} ∪ {v0, v1, v2};
(F9) u4v+2 = {u0, u1, u2, u3} ∪ {v0, v1};
(F10) u3v+5 = {u0, u1, u2, u5} ∪ {v0, v1, v2, v3, v4};
(F11) u3v+4 = {u0, u1, u2} ∪ {v0, v1, v2, v3};
(F12) u3v+3 = {u0, u1, u2} ∪ {v0, v1, v2};
(F13) u2v+5 = {u0, u1} ∪ {v0, v1, v2, v3, v4};
(F14) u2v+4 = {u0, u1} ∪ {v0, v1, v2, v3};
(F15) u1v+5 = {u0} ∪ {v0, v1, v2, v3, v4}.
Proof. In view of Remark 4.19 and Corollary 4.20, we may assume that the points of P are
placed as in Figure 15. Moreover, by symmetry, we only need to verify the case u = x and
v = y. For brevity, form ∈ {0, . . . , 5}, we letXm := {xi
∣∣i ≤ m} and Ym := {yi∣∣i ≤ m}.
(F1): From (D3), we know that x4x+5 = X3 ∪ Y3. We claim that the first point p ∈ P
that x4x5 finds when it is rotated counterclockwise around x5 is y4. From (D4), we know
that x3x+5 = X2 ∪ Y4. Then p = y4, and so x5y
+
4 = X3 ∪ Y3, as required.
(F2): We know that x3x+5 = X2 ∪ Y4 by (D4). We claim that the first point p ∈ P that
x3x5 finds when it is rotated counterclockwise around x5 is y5. Indeed, from (D1), (E8),
and (E12), we know that y5 ∈ xjx+5 for j = 0, 1, 2, respectively. These imply that p /∈ X2,
and so p = y5. Then x5y+5 = X2 ∪ Y4, as required.
(F3): We know that x4x+5 = X3 ∪ Y3 by (D3). We claim that the first point p ∈ P
that x4x5 finds when it is rotated clockwise around x5 is y3. Indeed, by applying (E7),
(E10), and (E13) to j = 0, 1 and j = 2 (with u = y and v = z), respectively, we have that
X ⊂ yjy−3 , and so x5 ∈ yjy
−
3 . These imply that p /∈ Y2. This and the fact that x5y
+
0 = X4
imply that p = y3. Then x5y+3 = X4 ∪ Y2, as required.
(F4): We know that x5y+3 = X4 ∪ Y2 by (F3). We claim that the first point p ∈ P
that x5y3 finds when it is rotated clockwise around x5 is y2. Indeed, by applying (E6) and
(E11) to j = 0 and j = 1 (with u = y and v = z), respectively, we have that X ⊂ yjy−2 ,
and so x5 ∈ yjy−2 . These imply that p /∈ Y1. This and the fact that x5y
+
0 = X4 imply that
p = y2. Then x5y+2 = X4 ∪ Y1, as required.
(F5): We know that x5y+2 = X4 ∪ Y1 by (F4). We claim that the first point p ∈ P that
x5y2 finds when it is rotated clockwise around x5 is y1. Indeed, by taking u = y in (E7),
we have that x5 ∈ y0y−1 , and so p ̸= y0. This and the fact that x5y
+
0 = X4 imply that
p = y1. Then x5y+1 = X4 ∪ Y0, as required.
(F6): We know that x4x+5 = X3 ∪ Y3 by (D3). We claim that the first point p ∈ P
that x4x5 finds when it is rotated counterclockwise around x4 is y4. Indeed, by taking
u = y and v = z in D3) we get x4 ∈ y4y−5 , and so p ̸= y5. This and the fact that
x0x
+
4 = {x1, x2, x3, x5} ∪ Y imply that p = y4. Then x4y
+
4 = X3 ∪ Y3 ∪ {x5}, as
required.
(F7): We know that x4y+4 = X3 ∪ Y3 ∪ {x5} by (F6). We claim that the first point
p ∈ P that x4y4 finds when it is rotated counterclockwise around x4 is y5. Indeed, from
(D2), we know that x0x+4 = {x1, x2, x3, x5}∪Y . These imply that p /∈ X , and so p = y5.
Then x4y+5 = X3 ∪ Y4 ∪ {x5}, as required.
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 25
(F8): We know that x4x+5 = X3 ∪ Y3 by (D3). We claim that the first point p ∈ P that
x4x5 finds when it is rotated clockwise around x4 is y3. Indeed, by applying E7), E10), and
E13) to j = 0, 1 and j = 2 (with u = y and v = z), respectively, we have that X ⊂ yjy−3 ,
and so x4 ∈ yjy−3 . These imply that p /∈ Y2. From Proposition 4.3(2), we know that
X3 ⊂ x4y+1 , and so p /∈ X3. All these facts imply that p = y3, and so x4y
+
3 = X3 ∪Y2, as
required.
(F9): We know that x4y+3 = X3 ∪ Y2 by (F8). We claim that the first point p ∈ P
that x4y3 finds when it is rotated clockwise around x4 is y2. Indeed, by applying (E6) and
(E11) to j = 0 and j = 1 (with u = y and v = z), respectively, we have that X ⊂ yjy−2 ,
and so x4 ∈ yjy−2 . These imply that p /∈ Y1. From this and (D3) it follows that p = y2,
and so x4y+2 = X3 ∪ Y1, as required.
(F10): We know that x3x+5 = X2∪Y4 by (D4). We claim that the first point p ∈ P that
x3x5 finds when it is rotated counterclockwise around x3 is y5. Indeed, by applying (E7),
(E10), and (E13) to j = 0, 1 and j = 2 (with u = x and v = y), respectively, we have that
Y ⊂ xjx+3 , and so y5 ∈ xjx
+
3 . These imply that p /∈ X2. From this and E5) it follows that
p = y5, and so x3y+5 = X2 ∪ Y4 ∪ {x5}, as required.
(F11): We know that x3x+5 = X2 ∪ Y4 by D4). We claim that the first point p ∈ P that
x3x5 finds when it is rotated clockwise around x3 is y4. Indeed, by applying (D2), (E5),
(E4), and (E5) to j = 0, 1, 2 and j = 3 (with u = y and v = z), respectively, we have
that X ⊂ yjy−4 , and so x3 ∈ yjy
−
4 . These imply that p /∈ Y3. From Proposition 4.3(2),
we know that x4 ∈ x3y−2 , and so p ̸= x4. All these facts imply that p = y4, and so
x3y
+
4 = X2 ∪ Y3, as required.
(F12): We know that x3y+4 = X2 ∪ Y3 by (F11). We claim that the first point p ∈ P
that x3y4 finds when it is rotated clockwise around x3 is y3. Indeed, by applying (E7),
(E10), and (E13) to j = 0, 1 and j = 2 (with u = y and v = z), respectively, we have that
X ⊂ yjy−3 , and so x3 ∈ yjy
−
3 . These imply that p /∈ Y2. By taking u = x in (E5) and (D4),
we have that y4 ∈ x3x+4 and y4 ∈ x3x
+
5 , respectively. These imply that p /∈ {x4, x5}. All
these facts imply that p = y3, and so x3y+3 = X2 ∪ Y2, as required.
(F13): From Proposition 4.3(2), we know that x2y+3 = X1 ∪Y2. We claim that the first
point p ∈ P that x2y3 finds when it is rotated counterclockwise around x2 is y4. Indeed,
by applying (E6) and (E11) to j = 0 and j = 1 (with u = x and v = y), respectively, we
have that Y ⊂ xjx+2 , and so p /∈ {x0, x1}. Finally, by applying (E4), (E12), and (E13) to
j = 4, 5 and j = 3 (with u = x and v = y), we have that p ̸= x4, p ̸= x5 and p ̸= x3,
respectively. All these facts imply that p = y4, and so x2y+4 = X1 ∪ Y3, as required.
(F14): We know that x2y+4 = X1 ∪ Y3 by (F13). We claim that the first point p ∈ P
that x2y4 finds when it is rotated counterclockwise around x2 is y5. As in (F13) we can
deduce from (E6) and (E11) that p /∈ {x0, x1}. Again, as in (F13) we can deduce from
(E4), (E12), and (E13) that p ̸= x4, p ̸= x5 and p ̸= x3, respectively. All these facts imply
that p = y5, and so x2y+5 = X1 ∪ Y4, as required.
(F15): We know that x2y+5 = X1 ∪ Y4 by F14). We claim that the first point p ∈ P
that x2y5 finds when it is rotated counterclockwise around y5 is x1. Indeed, from Proposi-
tion 4.3(2), we know that y5z+0 = Y4. From the last two equations we have that p ∈ X1 =
{x0, x1}. Again, from Proposition 4.3(2), we know that x0y+5 = Y4, and so p = x1. Then
x1y
+
5 = X0 ∪ Y4, as required.
26 Ars Math. Contemp. 24 (2024) #P2.10
4.6 Conclusion of the proof of Lemma 3.1
In Tables 1 and 2 we give a summary of the results in Propositions 4.3(2)(b), 4.21, 4.22,
and 4.24. These tables assume that u ∈ {x, y, z} and v = σ(u), where σ is the automor-
phism of {x, y, z} defined in Corollary 4.20, namely x σ7→ y, y σ7→ z, and z σ7→ x.
In particular, for each u ∈ {x, y, z} and m,n ∈ {0, . . . , 5} with m < n, the set umu+n
is given in Table 1. This also determines the set unu+m, since unu
+
m = umu
−
n , and umu
−
n
is evidently determined from umu+n . Thus the information in Table 1 suffices to determine
pq+ whenever pq is a monochromatic edge of P .
Now for each u ∈ {x, y, z} and each m,n ∈ {0, . . . , 5}, the set umv+n is given in
Table 2. This also determines the set vnu+m, since vnu
+
m = umv
−
n , and umv
−
n is evidently
determined from umv+n . Thus the information in Table 2 suffices to determine pq
+ when-
ever pq is a bichromatic edge of P . □
uiu
+
j for each uiuj ∈ Emonk (P ) Classification of uiuj Equality stated in
u0u
+
5 = {v0, . . . , v5} 6-edge (D1)
u0u
+
4 = {u1, u2, u3, u5} ∪ {v0, . . . , v5} 6-edge (D2)
u0u
+
3 = {u1, u2, u5} ∪ {v0, . . . , v5} 7-edge (E7)
u0u
+
2 = {u5} ∪ {v0, . . . , v5} 7-edge (E6)
u0u
+
1 = {u2, u5} ∪ {v0, . . . , v5} 8-edge (E7)
u1u
+
5 = {u0} ∪ {v0, . . . , v5} 7-edge (E8)
u1u
+
4 = {u2, u3, u5} ∪ {v0, . . . , v5} 7-edge (E5)
u1u
+
3 = {u2, u5} ∪ {v0, . . . , v5} 8-edge (E10)
u1u
+
2 = {u0, u5} ∪ {v0, . . . , v5} 8-edge (E11)
u2u
+
5 = {u0, u1} ∪ {v0, . . . , v5} 8-edge (E12)
u2u
+
4 = {u5} ∪ {v0, . . . , v5} 7-edge (E4)
u2u
+
3 = {u4, u5} ∪ {v0, . . . , v5} 8-edge (E13)
u3u
+
5 = {u0, u1, u2} ∪ {v0, . . . , v4} 8-edge (D4)
u3u
+
4 = {u2, u5} ∪ {v0, . . . , v5} 8-edge (E5)
u4u
+
5 = {u0, . . . , u3} ∪ {v0, . . . , v3} 8-edge (D3)
Table 1: All the monochromatic edges of P .
5 Concluding remarks
In this work we finally have given the full proof of Theorem 1.2, which was announced at
the EuroComb’11 conference [1].
As we mentioned in the Introduction, the exact rectilinear crossing number of Kn is
known only for n ≤ 27 and n = 30 [3, 7, 8, 9, 10]. In [2] and [6] we can find non-
isomorphic crossing-minimal rectilinear drawings of Kn for both n = 24 and n = 30.
On the other hand, from [6] and the main result of this work, now we know that there
is a unique (up to order type isomorphism) crossing-minimal rectilinear drawing of Kn,
for n = 6, 12, 18. Thus, a plausible conjecture is that K6m has several crossing-minimal
rectilinear drawings for each integer m ≥ 4.
We close this paper with a discussion on a question raised by an anonymous reviewer
of an earlier version of this paper: to what degree would it be possible to get a computer-
assisted proof of Theorem 1.2?
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 27
uv+ for each uv ∈ Ebik (P ) Classification of uv Equality stated in
u0v
+
5 = {v0, . . . , v4} 5-edge Proposition 4.3(2)
u0v
+
4 = {v0, v1, v2, v3} 4-edge Proposition 4.3(2)
u0v
+
3 = {v0, v1, v2} 3-edge Proposition 4.3(2)
u0v
+
2 = {v0, v1} 2-edge Proposition 4.3(2)
u0v
+
1 = {v0} 1-edge Proposition 4.3(2)
u0v
+
0 = ∅ 0-edge Proposition 4.3(2)
u1v
+
5 = {u0} ∪ {v0, . . . , v4} 6-edge (F15)
u1v
+
4 = {u0} ∪ {v0, v1, v2, v3} 5-edge Proposition 4.3(2)
u1v
+
3 = {u0} ∪ {v0, v1, v2} 4-edge Proposition 4.3(2)
u1v
+
2 = {u0} ∪ {v0, v1} 3-edge Proposition 4.3(2)
u1v
+
1 = {u0} ∪ {v0} 2-edge Proposition 4.3(2)
u1v
+
0 = {u0} 1-edge Proposition 4.3(2)
u2v
+
5 = {u0, u1} ∪ {v0, . . . , v4} 7-edge (F14)
u2v
+
4 = {u0, u1} ∪ {v0, v1, v2, v3} 6-edge (F13)
u2v
+
3 = {u0, u1} ∪ {v0, v1, v2} 5-edge Proposition 4.3(2)
u2v
+
2 = {u0, u1} ∪ {v0, v1} 4-edge Proposition 4.3(2)
u2v
+
1 = {u0, u1} ∪ {v0} 3-edge Proposition 4.3(2)
u2v
+
0 = {u0, u1} 2-edge Proposition 4.3(2)
u3v
+
5 = {u0, u1, u2, u5} ∪ {v0, . . . , v4} 7-edge (F10)
u3v
+
4 = {u0, u1, u2} ∪ {v0, v1, v2, v3} 7-edge (F11)
u3v
+
3 = {u0, u1, u2} ∪ {v0, v1, v2} 6-edge (F12)
u3v
+
2 = {u0, u1, u2} ∪ {v0, v1} 5-edge Proposition 4.3(2)
u3v
+
1 = {u0, u1, u2} ∪ {v0} 4-edge Proposition 4.3(2)
u3v
+
0 = {u0, u1, u2} 3-edge Proposition 4.3(2)
u4v
+
5 = {u0, u1, u2, u3, u5} ∪ {v0, . . . , v4} 6-edge (F7)
u4v
+
4 = {u0, u1, u2, u3, u5} ∪ {v0, . . . , v3} 7-edge (F6)
u4v
+
3 = {u0, u1, u2, u3} ∪ {v0, v1, v2} 7-edge (F8)
u4v
+
2 = {u0, u1, u2, u3} ∪ {v0, v1} 6-edge (F9)
u4v
+
1 = {u0, u1, u2, u3} ∪ {v0} 5-edge Proposition 4.3(2)
u4v
+
0 = {u0, u1, u2, u3} 4-edge Proposition 4.3(2)
u5v
+
5 = {u0, u1, u2} ∪ {v0, . . . , v4} 8-edge (F2)
u5v
+
4 = {u0, . . . , u3} ∪ {v0, . . . , v3} 8-edge (F1)
u5v
+
3 = {u0, . . . , u4} ∪ {v0, v1, v2} 8-edge (F3)
u5v
+
2 = {u0, . . . , u4} ∪ {v0, v1} 7-edge (F4)
u5v
+
1 = {u0, . . . , u4} ∪ {v0} 6-edge (F5)
u5v
+
0 = {u0, u1, u2, u3, u4} 5-edge Proposition 4.3(2)
Table 2: All the bichromatic edges of P .
28 Ars Math. Contemp. 24 (2024) #P2.10
At the beginning of this project we asked ourselves the same question, but we are con-
vinced that a traditional proof might be easier to verify. It is worth mentioning that a heav-
ily computer-assisted proof seems to be out of reach, most likely involving several hundred
million CPU hours. On the other hand, we believe that a partially computer-assisted proof
would be more difficult to follow and perhaps also less reliable. Using computer-assisted
proofs needs a very careful preparation and description of what is done, and proofs of the
correctness of the results. The code must be explained in full detail, as well as how the
program can be executed (including the operating system, compiler versions, etc.). We
believe that in this particular case the task of verifying all this information would end up
being more taxing on the reader than the current purely theoretical proof.
ORCID iDs
Bernardo M. Ábrego https://orcid.org/0000-0003-4695-5454
Silvia Fernández–Merchant https://orcid.org/0000-0003-2080-106X
Oswin Aichholzer https://orcid.org/0000-0002-2364-0583
Jesús Leaños https://orcid.org/0000-0002-3441-8136
Gelasio Salazar https://orcid.org/0000-0002-8458-3930
References
[1] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, J. Leaños and G. Salazar, There is a
unique crossing-minimal rectilinear drawing of K18, in: Extended abstracts of the sixth Euro-
pean conference on combinatorics, graph theory and applications, EuroComb 2011, Budapest,
Hungary, August 29 – September 2, 2011, Elsevier, Amsterdam, pp. 547–552, 2011, doi:
10.1016/j.endm.2011.09.089, https://doi.org/10.1016/j.endm.2011.09.089.
[2] B. M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños and G. Salazar, 3-symmetric and
3-decomposable geometric drawings of Kn, Discrete Appl. Math. 158 (2010), 1240–1258, doi:
10.1016/j.dam.2009.09.020, https://doi.org/10.1016/j.dam.2009.09.020.
[3] B. M. Ábrego, M. Cetina, S. Fernández-Merchant, J. L. nos and G. Salazar, On ≤ k-
edges, crossings, and halving lines of geometric drawings of kn, Discrete Comput. Geom.
48 (2012), 192–215, doi:10.1007/s00454-012-9403-y, https://doi.org/10.1007/
s00454-012-9403-y.
[4] B. M. Ábrego and S. Fernández-Merchant, A lower bound for the rectilinear crossing number,
Graphs Comb. 21 (2005), 293–300, doi:10.1007/s00373-005-0612-5, https://doi.org/
10.1007/s00373-005-0612-5.
[5] B. M. Ábrego, S. Fernández-Merchant and G. Salazar, The rectilinear crossing num-
ber of Kn: closing in (or are we?), in: Thirty Essays on Geometric Graph Theory,
Springer, Berlin, pp. 5–18, 2013, doi:10.1007/978-1-4614-0110-0 2, https://doi.org/
10.1007/978-1-4614-0110-0_2.
[6] O. Aichholzer, http://www.ist.tugraz.at/aichholzer/research/rp/
triangulations/crossing/.
[7] O. Aichholzer, J. Garcia, D. Orden and P. Ramos, New lower bounds for the number of (≤ k)-
edges and the rectilinear crossing number of Kn, Discrete Comput. Geom. 38 (2007), 1–14, doi:
10.1007/s00454-007-1325-8, https://doi.org/10.1007/s00454-007-1325-8.
[8] O. Aichholzer, J. Garcı́a, D. Orden and P. Ramos, New results on lower bounds for the num-
ber of (⩽ k)-facets, in: Proceedings of the 4th European conference on combinatorics, graph
B. M. Ábrego et al.: There is a unique crossing-minimal rectilinear drawing of K18 29
theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007, Elsevier, Am-
sterdam, pp. 189–193, 2007, doi:10.1016/j.endm.2007.07.033, https://doi.org/10.
1016/j.endm.2007.07.033.
[9] O. Aichholzer and H. Krasser, Abstract order type extension and new results on the recti-
linear crossing number, Comput. Geom. 36 (2007), 2–15, doi:10.1016/j.comgeo.2005.07.005,
https://doi.org/10.1016/j.comgeo.2005.07.005.
[10] M. Cetina, C. Hernández-Vélez, J. Leaños and C. Villalobos, Point sets that minimize (≤ k)-
edges, 3-decomposable drawings, and the rectilinear crossing number of K30, Discrete Math.
311 (2011), 1646–1657, doi:10.1016/j.disc.2011.03.030, https://doi.org/10.1016/
j.disc.2011.03.030.
[11] R. K. Guy, A combinatorial problem, (Nabla) Bull. Malays. Math. Sci. Soc. 7 (1960), 68–72.
[12] L. Lovász, K. Vesztergombi, U. Wagner and E. Welzl, Convex quadrilaterals and k-sets, in:
Towards a Theory of Geometric Graphs, American Mathematical Society (AMS), Providence,
RI, pp. 139–148, 2004.