Also available on http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 32–37
An Optimality Criterion for the Crossing Number
László A. Székely †
Department of Mathematics
University of South Carolina, Columbia, SC 29208, USA
Received 30 September 2007, accepted 22 February 2008, published online 19 June 2008
Abstract
A sufficient condition is given that a certain drawing minimizes the crossing number. The
condition is in terms of intersections in an arbitrary set system related to the drawing, and is
like a correlation inequality.
Keywords: Graph drawing, crossing number.
Math. Subj. Class.: 05C10, 05C62
1 Definitions
First I recall from [5] definitions for two kinds of drawings, in which different kinds of cross-
ing numbers can be conveniently set.
A drawing D of a finite graph G on the plane is an injection φ from the vertex set V (G)
into the plane, and a mapping of the edge set E(G) into the set of simple plane curves, i.e.
homeomorphic images of the interval [0, 1], such that the curve corresponding to the edge
e = uv has endpoints φ(u) and φ(v), and contains no more points from the image of φ.
We say that two edges in a drawing cross in a certain point of the plane, or the point
is a crossing point of the two edges, if this point belongs to the interiors of the curves
representing the edges. The number of crossings cr(D) in the drawing D is the sum of the
number of crossing points for all unordered pairs of edges.
A drawing D is normal if it satisfies (i), (ii) and (iii):
(i) any two of the curves have finitely many points in common; and
(ii) no two curves have a point in common in a tangential (touching) way
(i.e. defining locally the “left side” and the “right side” of the curves at the common point,
both curves are present at both sides of each in every small neighborhood of that point);
†Research partially supported by the NSF Grants 030 2307 and 070 1111.
E-mail address: szekely@math.sc.edu (László A. Székely)
Copyright c© 2008 DMFA – založništvo
L. A. Székely: An Optimality Criterion for the Crossing Number 33
(iii) no point of the plane belongs to the interior of three curves, each representing an edge of
the graph.
A drawing D is nice, if it is normal, and in addition satisfies
(iv) no two adjacent edges (i.e. edges sharing an endpoint) cross; and
(v) any two edges cross at most once.
The crossing number CR(G) of the graph G is the minimum of cr(D) over all drawings
of G. We call a drawing D optimal (for CR) if it realizes cr(D) = CR(G). It is easy
to see that an optimal drawing must satisfy (i) and (ii), and a little work shows that it also
must satisfy (iv) and (v). (Condition (iii) makes little difference other than allowing a simpler
definition of CR(G) by counting crossings inD, instead of looking at pairs of edges.) There-
fore, we have an equivalent definition of CR(G): the minimum of cr(D) over all normal,
nice drawings of G.
Pach and Tóth [3] introduced two new variants of the crossing number problem:
the pairwise crossing number CR-PAIR(G) is equal to the minimum number of unordered
pairs of edges that cross each other at least once (i.e. they are counted once instead of as
many times they cross), over all normal drawings of G; and
the odd crossing number CR-ODD(G) is equal to the minimum number of unordered pairs
of edges that cross each other odd times, over all normal drawings of G.
In Tutte’s work [8] another kind of crossing number is implicit:
the independent-odd crossing number. Let cr-iodd(D) denote the number of unordered pairs
of non-adjacent edges that cross each other odd times in a normal drawing D of the graph G,
and let CR-IODD(G) denote the minimum of cr-iodd(D) over all normal drawings D of
G.
The following chain of inequalities is obvious from the definitions:
CR-IODD(G) ≤ CR-ODD(G) ≤ CR-PAIR(G) ≤ CR(G). (1)
No example of strict inequality was known for a long time, but in a recent work Pelsmajer,
Schaefer and Štefankovič [4] showed examples of graphs G with CR-ODD(G) < CR(G).
2 The criterion
Let us associate with every edge e = {x, y} ∈ E(G) an arbitrary vertex set Ae ⊆ V (G) \
{x, y}. If the edges e and f are non-adjacent, then we define the parity of this edge pair as 0
or 1 according to
par(e, f) = |e ∩Af |+ |f ∩Ae| modulo 2. (2)
Let us be given a normal drawing D of the simple graph G. If non-adjacent edges e, f cross
in D odd times, then we write e ×oddD f , otherwise write e ×evenD f . Later, if not specified
otherwise, single summations written for pairs of edges mean summations are for unordered
pairs of non-adjacent edges.
Theorem 1. Using the notation above, the condition that
for all e 7→ Ae assignments
∑
par(e,f)=1
e×odd
D
f
1 ≤
∑
par(e,f)=1
e×even
D
f
1 (3)
holds, is equivalent to the CR-IODD-optimality of D. Furthermore, if D is nice, then D is
optimal for CR as well.
34 Ars Mathematica Contemporanea 1 (2008) 32–37
It is hard to verify whether this criterion holds, since checking the condition for all pos-
sible sets Ae requires exponential time. This not surprising, in view of the NP-completeness
of the decision problems CR(G) ≤ k (Garey and Johnson [1]), of CR-ODD(G) ≤ k
(Pach and Tóth [3]), and the NP-hardness of the decision problem CR-PAIR(G) ≤ k (Pach
and Tóth [3]). However, inequality (3), which looks like a correlation inequality formu-
lated about random edge pairs, may have a less exhaustive and more theoretical proof for
some graphs and their drawings that show a high degree of structure. A natural candidate
would be Zarankiewicz’ drawing of the complete bipartite graph, which is nice and conjec-
tured to be optimal. For the fascinating history of Turán’s Brick Factory Problem [7] and the
Zarankiewicz drawing [10], see [6] and the classic [2]. For the best current result, see [9].
Note that if the second part of the criterion applies as the drawing is nice, then CR(G)
equals to CR-IODD(G).
3 Proof of the criterion
We recall what we need from [5]. Let us be given an arbitrary cyclic order C = v1, v2, ..., vn
of the vertices of a simple graph G. We say that two non-adjacent edges of G, say xy and
uz are in acyclic order, if the cyclic order C restricted to these 4 vertices is x, u, y, z or
x, z, y, u. Otherwise, two non-adjacent edges are in cyclic order. These two relations are
clearly symmetric. In [5] we defined the relation OC of non-adjacent edges of G as follows:
OC(xy, uz) =
{
1 if xy and uz are in cyclic order,
0 otherwise.
(4)
Note that OC(xy, uz) = OC(xy, zu) = OC(uz, xy).
Let us be given a normal drawing D of the graph G and a fixed OC . In [5] we associated
with the curve representing the edge e = {x, y} ∈ E(G) a particular function Qxy : V (G) \
{x, y} → {1,−1}, which also depends on the binary relation OC , such that changing any
function Qxy to −Qxy makes no difference; and we also observed in [5] that any set of
functions
Q =
{
Qab : V (G) \ {a, b} → {1,−1} : ab ∈ E(G)
}
(5)
comes from some normal drawing through this association.
(Though just citing (6) would suffice to prove our theorem without even giving the def-
inition of Qxy here, for the geometrically inclined Reader, we sketch the definition of Qxy .
Deform the normal drawing D without pulling edges over vertices and keeping normality
such that the vertex set of G lies on the unit circle around the origin in cyclic order C. Con-
sider the following—possibly self-intersecting—closed curve q in the plane extended with
the point ∞: the ray from x to ∞ not passing through the origin, the ray from ∞ to y not
passing through the origin, and the curve representing the yx edge in the deformed drawing.
It is shown in [5] that this closed curve defines two classes of vertices of V (G) \ {x, y} (one
of them can be empty) such that a generic curve connecting u, v ∈ V (G) \ {x, y} passes
through q odd number of times if and only if u and v belong to different classes. Qxy takes
value 1 on the elements of one equivalence class, and takes value −1 on the elements of the
other equivalence class.)
L. A. Székely: An Optimality Criterion for the Crossing Number 35
Formula (20) in [5] shows that xy ×oddD uz holds if and only if
[1−OC(xy, uz)]
1 +Qxy(u)Qxy(z)Quz(x)Quz(y)
2
+ OC(xy, uz)
1−Qxy(u)Qxy(z)Quz(x)Quz(y)
2
(6)
is equal to 1, and xy ×evenD uz holds if and only if (6) is 0. We keep (6) in this ugly form
that we will use in our calculations, but will elucidate (6) in (8). (There is a typo after (20)
in [5], as the minus sign is missing in the formula Pxy(uz) = −Qxy(u)Qxy(z), but this is
irrelevant regarding the conclusions.) Let us introduce the abbreviation
Q(xy, uz) = Qxy(u)Qxy(z)Quz(x)Quz(y). (7)
Exploiting (6), we obtain
xy ×oddD uz ⇔ [OC(xy, uz) = 0 ∧ Q(xy, uz) = 1]
∨ [OC(xy, uz) = 1 ∧ Q(xy, uz) = −1];
xy ×evenD uz ⇔ [OC(xy, uz) = 0 ∧ Q(xy, uz) = −1]
∨ [OC(xy, uz) = 1 ∧ Q(xy, uz) = 1]. (8)
Summing up (6) for all ordered pairs of non-adjacent edges, one obtains that the number of
edge pairs crossing odd times in every normal drawing D is
N
2
− 1
2
∑
xy∈E(G)
∑
uz∈E(G)
{u,z}∩{x,y}=∅
{
OC(xy, uz)−
1
2
}
Qxy(u)Qxy(z)Quz(x)Quz(y), (9)
where N denotes the number of unordered pairs of non-adjacent edges in G. (Though there
are many ways to define the binary relation OC , all of them yield formally the same formula
(9), since Q in (9) depends on the choice of the relation OC .)
Let us fix the graph G, and the binary relation OC . Consider two normal drawings of G,
an arbitrary D′, and a D optimal for CR-IODD. Let Q and Q′ denote the set of functions
associated with D and D′, respectively. According to (9), the optimality of D′ is equivalent
to the inequality
∑
xy∈E(G)
∑
uz∈E(G)
{u,z}∩{x,y}=∅
{
OC(xy, uz)−
1
2
}
Q′xy(u)Q
′
xy(z)Q
′
uz(x)Q
′
uz(y) (10)
≤
∑
xy∈E(G)
∑
uz∈E(G)
{u,z}∩{x,y}=∅
{
OC(xy, uz)−
1
2
}
Qxy(u)Qxy(z)Quz(x)Quz(y). (11)
For every e = {x, y} ∈ E(G), set
A{x,y} = {z ∈ V (G) \ {x, y} : Q{x,y}(z)Q′{x,y}(z) = −1}. (12)
Using the definition (2), it is not difficult to see that
Q′xy(u)Q
′
xy(z)Q
′
uz(x)Q
′
uz(y) = Qxy(u)Qxy(z)Quz(x)Quz(y)(−1)par(xy,uz). (13)
36 Ars Mathematica Contemporanea 1 (2008) 32–37
Using (13) and the abbreviation (7), one can equivalently rewrite (10–11), based on a case
analysis for OC , as ∑
xy,uz∈E(G)
OC(xy,uz)=0
{
1− (−1)par(xy,uz)
}
Q(xy, uz) (14)
≤
∑
xy,uz∈E(G)
OC(xy,uz)=1
{
1− (−1)par(xy,uz)
}
Q(xy, uz). (15)
At this point we claim the following identities for (14) and (15), which we put into a less
formal summation: ∑
OC(xy,uz)=0
par(xy,uz)=1
Q(xy, uz) (16)
=
∑
OC(xy,uz)=0
par(xy,uz)=1
xy×odd
D
uz
Q(xy, uz) +
∑
OC(xy,uz)=0
par(xy,uz)=1
xy×even
D
uz
Q(xy, uz) (17)
=
∑
OC(xy,uz)=0
par(xy,uz)=1
xy×odd
D
uz
1−
∑
OC(xy,uz)=0
par(xy,uz)=1
xy×even
D
uz
1 (18)
and ∑
OC(xy,uz)=1
par(xy,uz)=1
Q(xy, uz) (19)
=
∑
OC(xy,uz)=1
par(xy,uz)=1
xy×even
D
uz
Q(xy, uz) +
∑
OC(xy,uz)=1
par(xy,uz)=1
xy×odd
D
uz
Q(xy, uz) (20)
=
∑
OC(xy,uz)=1
par(xy,uz)=1
xy×even
D
uz
1−
∑
OC(xy,uz)=1
par(xy,uz)=1
xy×odd
D
uz
1. (21)
The equalities (18) = (17), and (20) = (21) follow from the fact, that the parity of the number
of crossings of xy and uz, together with the value of OC(xy, uz) determines the value of
Q(xy, uz) as 1 or −1, as substituted. This follows from (8). Finally, rewrite the inequality
(14) ≤ (15) into the equivalent form (18) ≤ (21). Move the negative terms to the other side
in the inequality (18) ≤ (21), to obtain∑
par(xy,uz)=1
xy×odd
D
uz
1 ≤
∑
par(xy,uz)=1
xy×even
D
uz
1, (22)
and we proved the equivalence part of Theorem 1. Therefore, if (3) holds, then the number
of edge pairs crossing odd times in D is as small as possible. If D is nice, then the number of
crossings in D, cr(D), is equal to the number of non-adjacent edge pairs crossing odd times,
cr-iodd(D). Therefore
CR-IODD(G) ≤ CR(G) ≤ cr(D) = cr−iodd(D) = CR-IODD(G),
L. A. Székely: An Optimality Criterion for the Crossing Number 37
implying that D is optimal drawing for CR(G).
References
[1] M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM J. Alg. Discrete Methods
4 (1983), 312–316.
[2] R. K. Guy, The decline and fall of Zarankiewicz’s theorem, in F. Harary (ed.), Proof Techniques
in Graph Theory, Academic Press, New York, London, 1969, 63–69.
[3] J. Pach and G. Tóth, Which crossing number is it anyway? in: Proc. 39th Annual Symposium on
Foundation of Computer Science, IEEE Press, Baltimore, 1998, 617–626; and J. Comb. Theory
Ser. B 80 (2000), 225–246.
[4] M. J. Pelsmajer, M. Schaefer and Štefankovič, Odd crossing number is not crossing number, in:
Graph Drawing, Lecture Notes in Computer Science 3843, Springer, Berlin, 2006, 386–396.
[5] L. A. Székely, A successful concept for measuring non-planarity of graphs: the crossing number,
Discrete Math. 276 (2003), 1–3, 331–352.
[6] L. A. Székely, Zarankiewicz crossing number conjecture, in: M. Hazewinkel (ed.), Kluwer Ency-
clopaedia of Mathematics, Supplement III, Kluwer Academic Publishers, 2002, 451–452.
[7] P. Turán, A note of welcome, J. Graph Theory 1 (1977), 7–9.
[8] W. T. Tutte, Toward a theory of crossing numbers, J. Combinatorial Theory 8 (1970), 45–53.
[9] D. R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture J. Graph
Theory 17 (1993), 657–671.
[10] K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math. 41 (1954), 137–145.