The Graph Crossing Number and its Variants: A Survey

example, consider the pair crossing number in the scenario depicted in the right picture of

Figure 1; swapping the arcs, or even just rerouting one of the arcs along the adjacent edge

will lead to an increase in the pair crossing number, so the simple local redrawing moves

common for cr do not seem to work. It is open whether a pcr-minimal drawing may have

ber [231].

4Recent examples dening crossing number as pcr include textbooks in combinatorics [460, 451, 471],

and books in algorithms and complexity [41, 265, 36, 37].

the electronic journal of combinatorics (2017), #DS21

3

crossings between adjacent edges (this question is equivalent to whether pcr < pcr+, see

the entry on pair crossing number in Section 3).

Even for the standard crossing number this is not the end of the story for adjacent

crossings. Here is a quote from a recent paper on Albertsons conjecture: if G has chro-

matic number at least r, then cr(G) > cr(Kr).

A crossing of two edges e and f is trivial if e and f are adjacent or equal,

and it is non-trivial otherwise. A drawing is good if it has no trivial crossings.

The following is a well-known easy lemma.

Lemma 1.1. A drawing of a graph can be modied to eliminate all of

its trivial crossings, with the number of non-trivial crossings remaining the

same. [362]

The independent crossing number, cr(G), only counts crossings occurring between

independent edges. If Lemma 1.1 were true, it would imply that cr = cr, a question

thats open to the best of our knowledge.5 Fortunately, the use of Lemma 1.1 could be

eliminated in this case [361], but wouldnt it be nice if we could establish cr = cr and not

have to worry about adjacent crossings anymore? The left and middle picture of Figure 1

explain why Lemma 1.1 looks so convincing: crossings between adjacent edges can easily

be removed by local redrawing, but the right picture shows that this can create crossings

between non-adjacent pairs of edges. A proof of a result like Lemma 1.1 will require a

more global approach.

Question 2. Here are two simple-looking problems that illustrate our lack of understand-

ing of adjacent crossings. (i) Can subdividing an edge change cr of a graph? (ii) Suppose

a graph can be drawn on a surface so that all crossings in the drawing are between ad-

jacent edges. Can the graph be embedded in that surface? An answer to the second

question is known for the plane and the projective plane by virtue of the Hanani-Tutte

theorems for those surfaces [376], but not for any other surface.6 The rst question is

open.

While not nearly as common as the pcr versus cr problem, cr is occasionally dened as

the smallest number of independent crossings; this may again be due to the fact that for

straight-line drawings, adjacent edges do not cross. For example, Moon [346] in one of the

earliest papers on crossing numbers denes what amounts to the independent (geodesic)

spherical crossing number which equals the geodesic spherical crossing number, since

5Start with a cr-minimal drawing. By the lemma, all trivial crossings can be eliminated, only leaving

non-trivial crossings, that is, crossings that count towards cr, so cr of the resulting drawing is at most

cr. In the other direction, cr 6 cr follows from the denition.

6The Hanani-Tutte theorem for a surface is true if every graph which can be drawn on so that no

two independent edges cross an odd number of times is embeddable in . The Hanani-Tutte theorem is

known to be true for the plane (sphere) [120, 462] and the projective plane [376]. It is not known to be

true for any other surface, and it has been announced that it fails for surfaces of genus 4 and higher [196].

In terms of crossing numbers, the Hanani-Tutte condition can be expressed as saying that iocr (G) = 0

implies that cr (G) = 0 for all graphs G.

the electronic journal of combinatorics (2017), #DS21

4

geodesics representing adjacent edges do not cross on the sphere. Nahas [354] denes

the crossing number of Km,n as cr(Km,n). Papers on crossing minimization via linear

programming also often ignore variables that encode crossings between adjacent edges.

This is ne, of course, as the resulting program enforce that adjacent edges do not cross;

otherwise, they would compute cr.

Remark 3. As far as we know there are only two crossing number notions for which

the independent variant is known to dier from the regular variant, namely the odd

and the algebraic crossing number: there are graphs G for which iocr(G) < ocr(G) and

iacr(G) < acr(G) [197]. The same paper also shows that prohibiting crossings between

adjacent edges in monotone drawings can lead to an increase in the monotone odd crossing

number. The same is true for the local crossing number, see Footnotes 72 and 74, and

the simultaneous crossing number, see Footnote 100. For directed graphs, the bimodal

crossing number may require crossings between adjacent edges in an optimal drawing. (cid:7)

Crossing Lemma Variants

The crossing lemma, or crossing number inequality, established independently by Ajtai,

Chv tal, Newborn, Szemeredi [16] and Leighton [317], is one of the most celebrated (and

famous) results on crossing numbers.7 In its original form, it shows that cr(G) > c

m3/n2,

where n =

. How does it fare for other crossing number variants, and

pair and odd crossing number in particular? Crossing lemmas for other variants are listed

in the compendium below.

, and m =

E

V

|

|

|

|

|

|

|

3n.

V (G)

E(G)

, m =

6, where n =

The usual probabilistic proof of the crossing lemma for a crossing number proceeds

in three steps: rst, we observe that if (G) = 0, then G is planar, so Eulers formula

applies, and m 6 3n

. In a second step, we argue

that we can remove at most (G) edges from G to reduce to 0, so m

6,

In a third step, we consider a random subgraph G2 of

and, hence, (G) > m

G, keeping each vertex with probability p. The expected number of vertices and edges

E2

in G2 = (V 2, E2) are E(

) = p2m. Fix a -minimal drawing D of

|

G. Assuming each crossing in D which contributes to is caused by two independent

edges, a crossing is associated with four endpoints. For the crossing to survive in D2, the

induced drawing of G2, all four endpoints have to be kept, so E( (G2)) 6 p4 (G). Now

G2 fullls (G2) >

(by the second step), so, taking expected values, we get

np3 (assuming p > 0). Choosing p = 4n/m

p4 (G) > p2m

implies that (G) > 1/64m3/n2, as long as m > 4n (which we need so p 6 1).

V 2

|

|

pn, or (G) > mp2

) = pn and E(

(G) 6 3n

V 2

|

E2

3

|

|

|

|

|

For = cr, this proof works just ne, and its been claimed in the literature (e.g.

[365]) that this proof also works for pair and odd crossing numbers. But there are two

subtle problems. Consider the case = pcr, the case claimed by Leighton [317]: in the

second step, the pcr-minimal drawing D may contain crossings between dependent edges,

and those contribute to pcr. Since we do not know how to remove dependent crossings

in general without increasing pcr(D), we have to take dependent crossings into account;

7For a very readable introduction, see Terence Taos blog enty [450], which also discusses applications

to incidence geometry and sum-product estimates.

the electronic journal of combinatorics (2017), #DS21

5

since those survive with probability p3, we would get a substantially worse bound than

&(m3/n2) on pcr(G). Alon [21], and Tao and Vu in their book on additive combina-

torics [451] circumvent this problem by working with pcr, the independent pair crossing

number, in which only the number of crossings of independent pairs of edges are counted.

However, for that crossing number the second step is no longer obvious:

if we have a

drawing D with k independent pairs of edges crossing, then removing k edges yields a

drawing in which all remaining crossings are dependent. Is that graph planar? The an-

swer is yes, but it requires the Hanani-Tutte theorem (see Footnote 6) to prove so (at

least we are not aware of a direct proof).

Remark 4. Since the Hanani-Tutte theorem is not known to be true for the torus, this

means that we do not currently have a proof of the crossing lemma for pcr or pcr on the

torus. A positive answer to Question 2 (ii) would be sucient to settle the problem. For

the standard crossing number, extensions of the crossing lemma to arbitrary surfaces are

(cid:7)

known [429].

Pach and T th [369] work with = ocr, the odd crossing number, which only counts

pairs of edges crossing an odd number of times. They use Hanani-Tutte in the rst and

second steps, but in the third step again assume that a crossing is associated with four

endpoints, which may not be the case for ocr. However, their proof is essentially correct

if read for = iocr, the independent odd crossing number, which counts the number

of independent pairs of edges crossing an odd number of times. For iocr, the Hanani-

Tutte theorem guarantees that we can remove iocr(G) edges from G to make G planar,

ensuring the correctness of the rst and second steps. And since iocr by denition only

counts independent pairs, the argument in the third step also works. We conclude that

iocr(G) > 1/64m3/n2, as long as m > 4n. Since ocr, pcr, and pcr (as well as acr and

iacr) are all bounded below by iocr, this immediately proves the crossing lemma for all

these variants. The constant c = 1/64 in these cases is weaker than what is currently

known for cr, but seems hard to improve [365, Remark 4.2], though it was recently shown

c = 1/34.2 will work for pcr+ [11].

Conclusion

We are forewarned that there is some subtlety to dening the crossing number, but rather

than seeing this as an issue, this gives us an opportunity. J nos Pach once said, in

eect, we dont need more crossing numbers, we need fewer crossing numbers. As a

look at the compendium will show it may be too late for that. Some crossing number

variants may have arisen by mistake, but most were dened with a specic purpose in

mind. This purpose may be theoretical, aimed at developing a theory of crossing number

(as Tutte [462] did with his crossing chains and iacr) or it may be practical, aimed at

improving the layout of graphs (as in the Metro-line crossing minimization problem).

The recent growth of graph drawing research and crossing minimization problems for

very specic visualization tasks is important evidence for that. Some variants, such as

the local crossing number or the maximum rectilinear crossing number, are so fundamental

that they have been rediscovered over and over again under various names.

the electronic journal of combinatorics (2017), #DS21

6

This survey of crossing number variants follows two main goals: to collect as many

dierent types of crossing number variants from the literature as possible (unifying pre-

sentations and names), and to attempt a systematic description of what makes a crossing

number. The results of this second step are presented rst, in Section 2. The results of

the rst step are collected in the Compendium in Section 3. Originally, the paper was to

contain a section on the history of the crossing number, however, Beineke and Wilsons

Early History of the Brick Factory problem [60] and Sz kelys Tur ns brick factory

problem: the status of the conjectures of Zarankiewicz and Hill make this part mostly

superuous.

Remark 5 (Forerunners of Crossing Minimization in Sociology). David Eppstein [170]

discovered the earliest known references to (general) crossing minimization.8 They come

from sociology, more specically the area of sociometry which is concerned with measuring

(and depicting) social relationships: in discussing sociograms (essentially graphs), Bron-

fenbrenner [87] in 1945 writes that The arrangement of subjects on the diagram, while

haphazard in part, is determined largely by trial and error with the aim of minimizing

the number of intersecting lines. Sociograms were introduced in J.L. Morenos Who

Shall Survive [347] in 1934, however, the rst edition of that book, while containing

many interesting graph visualizations, does not seem to discuss crossing minimization. In

the later, 1953, edition [348],9 there is an interesting paragraph which reads: A readable

sociogram is a good sociogram. To be readable, the number of lines crossing must be min-

imized. This mantra occurs repeatedly in the literature on sociograms, and at least once

in an earlier paper by Borgatta [82] who writes: A readable diagram is a good diagram.

To be readable, the number of lines crossing must be minimized. This may be taken as

a primary principle in the construction of inter-action diagrams; the fewer the number of

lines crossing, the better the diagram. The problem, then, is to nd the procedure which

best minimizes the number of lines that cross in a diagram. Borgatta then outlines a

multi-stage heuristic for crossing minimization (start with a small number of high-degree

vertices, drawn far apart, add vertices by decreasing degree, redraw diagram to improve

drawings of subgroups), and illustrates his method by working out an example on 26

vertices and 43 edges, shown in Figure 2; his nal drawing uses two crossings (which is

optimal, since his graph contains two disjoint copies of K5).

The earliest reference (found so far) on crossing minimization seems to be a 1940

paper by Northway [359] in which she suggests the use of radial layouts; vertices (school

children) are placed at various distances from a center based on some quantity (their

scores); directed edges between them are drawn as straight-line arrows. She writes that

it has been convenient to use counters [. . . ]. These are moved in the circles to which

their score belongs and arranged to get the best t among the individuals, i.e., to

have as few long lines and crossing lines as possible. She also suggests that grouping

vertices by some characteristic (in her example, sex), simplies this task. These quotes

8There are earlier references to crossing minimization when it comes to specic families of graphs [123,

297, 439], but none that are as general as these.

9This edition is available online at http://www.asgpp.org/docs/WSS/wss%20index/wss%20index.

html

the electronic journal of combinatorics (2017), #DS21

7

(a)

(b)

Figure 2: Maybe the rst published instance of a crossing minimization, reducing 16

crossings in (a) to the optimal 2 crossings in (b). Taken (with permission) from a 1951

article in the journal Group Psychotherapy by Edgar F. Borgatta [82].

are quite remarkable, and one wonders whether there is more early material on crossing

(cid:7)

minimization that is unknown in the mathematical literature.

One aspect that remains to be studied, is the history of knot crossing numbers and

their inuence (or not) on graph crossing numbers. When it comes to methods of counting

crossings, it seems that knot crossing numbers led the way; e.g. Tuttes theory of cross-

ing numbers is based on counting crossings algebraically, as one would for the algebraic

crossing number in knot theory, and as Gau would have done hundreds of years ago [206,

page 271279].

Remark 6 (Axioms). What makes a crossing number a crossing number? We have chosen

a descriptive/extensional approach for this survey, however, the material collected here

may at some point make a basis for a prescriptive/intensional approach. As far as we know

there has never been an attempt to axiomatize the notion of crossing number, either as

the standard crossing number or as the family of crossing number variants. Although not

plentiful, there are some candidate axioms based on common crossing number properties.

Embeddability Crossing numbers are generally considered to be measures of non-

the electronic journal of combinatorics (2017), #DS21

8

planarity or non-embeddability. It seems natural then to require that if (G) = 0

for some crossing number in surface , then G is embeddable in . Let us call

this the embeddability axiom. For the standard crossing number this is true by de-

nition (on any surface). For the independent odd crossing number it amounts to the

Hanani-Tutte theorem (which is only known for the plane and the projective plane,

see Footnote 6). For the conuent crossing number and the string crossing num-

ber, the embeddability axiom fails (complete graphs have conuent embeddings and

there are non-planar string graphs). A stronger, quantitative version of this axiom

would require that the removal of at most (G) edges from G makes G planar. The

intuition behind this strengthened version is that each crossing is caused by two

edges, so a crossing can be eliminated by removing one of the participating edges.

This axiom holds for the standard crossing number by denition (on any surface),

and for the pair crossing number. It also holds for the independent odd crossing

number in the plane and the projective plane, by the Hanani-Tutte theorem (Foot-

note 6), but, by [196] it fails on surfaces of genus 4 and higher. It also fails for the

degenerate crossing number, in which more than two edges can cross in a crossing,

and for any of the crossing numbers based on maximization.

Embedding By the same measure of non-planarity argument, a graph G that can be

embedded in a surface should have crossing number (G) = 0. Let us call this

the embedding axiom. This axiom is trivially true for most crossing number variants,

although there are some notable exceptions including crossing numbers dened via

maximization (maximum crossing number, maximum rectilinear crossing number)

and crossing numbers that require certain drawing conventions (e.g. bimodal, bipar-

tite, convex, and orchard crossing numbers). For the rectilinear crossing number,

the axiom amounts to Farys (or Wagners or Steinitzs) theorem. It appears to be

an open problem whether the axiom holds for the geodesic crossing number on other

surfaces.10

Subgraph Monotonicity The subgraph monotonicity axiom requires that if G is a sub-

graph of H, then (G) 6 (H). This is true (and trivial) for nearly all crossing

number variants. We are aware of only two provable exceptions, the triple crossing

while triple-cr(K6,3) = 2 [449], and the con-

number, for which triple-cr(K5,3) =

uent crossing number (all complete graphs have conuent crossing number 0). For

the maximum crossing number, monotonicity is a well-known open problem even

if G is required to be an induced subgraph of H [395]. A stronger requirement

is topological minor monotonicity:

if G is a subdivision of a subgraph of H, then

(G) 6 (H). This is still true for a large number of crossing numbers, but is not

known to hold for any of the independent crossing number variants, like cr, and

typically fails for alternative representations (like the conuent crossing number).

In contrast, most crossing numbers do not satisfy minor-monotonicity which has led

to the denition of the minor (or minor-monotone) and the genus crossing numbers.

10An announcement of a solution in [454, page 312] may have been in error [455].

the electronic journal of combinatorics (2017), #DS21

9

Surface Monotonicity The surface monotonicity axiom requires that if surface has

smaller genus than surface , then > . We are not aware of any crossing

number that does not fulll this axiom. One could imagine sharper quantitative

versions of this axiom, for example if has smaller genus than , then (G) >

(G) unless (G) = 0.

One can imagine further axioms, for example based on what may be called the spectrum

. This notion has

of the crossing number of a graph G:

occasionally been studied, e.g. [198, 384] for the maximum crossing number, or [247] for

the edge crossing number. Harborth [244] showed that the spectrum of K14 under cr is not

a subset of the spectrum of K14 under the 2-page crossing number bkcr2, and conjectured

that K14 is the smallest complete graph for which the spectra of cr and bkcr2 dier.11

(D) : D is a drawing of G

{

}

It is probably unreasonable to expect an axiomatization of the (standard) crossing

number; however, it may be reasonable to attempt to axiomatize suciently many stan-

dard properties of the crossing number that would show why many of them allow a crossing

(cid:7)

lemma. Or why many of them can be bounded within each other.

2 A Systematic Approach

In this section we want to take a systematic approach to crossing number variants. The

discussion is based on the crossing number notions collected from the literature and pre-

sented in Section 3, and the reader is asked to look for denitions there if they are not

given in this section. Before reviewing crossing numbers, we begin with a discussion of

crossings themselves.

What is a crossing? Typically, a crossing is dened to be a common interior point of

two edges; hence, a shared endpoint (of two adjacent edges) is not considered a crossing.

This distinguishes a crossing from an intersection of two edges.12

The denition as given also distinguishes a crossing from the point in the plane at

which the crossing occurs (and this is good). The denition does, however, include points

in which two curves touch; this is of no consequence for the standard crossing number since

in crossing-minimal drawings no touching points occur, but for other variants, e.g. the

odd crossing number, counting touching points as crossings would trivialize the notion.

For Kleitman [294] a crossing requires that the two edges involve actually cross. This

requirement leads to other issues if not handled carefully: take a drawing of K5 with a

single crossing and replace the crossing with a short line segment (so the two edges involved

in the crossing run parallel for a short stretch). According to Kleitmans denition this

drawing is free of crossings (even though it has an innite number of intersection points).

This suggests the importance of restricting drawings to drawings with a nite number of

intersection points (which is what we will do) which causes a slight inconvenience when

11Harborth mentions an unpublished paper that seems to establish signicant parts of this conjecture.

12One subtlety already:

it excludes from the notion of crossing any intersection occurring when an

edge passes through a vertex, as opposed to ending there. Such intersections are typically prohibited, but

what happens if we allow them?

the electronic journal of combinatorics (2017), #DS21

10

dealing with conuent drawings: in conuent drawings of graphs edges seem to overlap

heavily. We resolve this by looking at conuent drawings not as drawings of the edges

and vertices of the graph, but as a drawing of branches and switches that represent the

underlying graph.

We return to a more formal denition of crossing in Section 2.2.1 after discussing basic

drawing conventions.

Figure 3: Drawing of K8 from de la Vera Cruz Recognitio Summularum with ribbons

crossing through each other. The image is taken from the online (public domain) version

of the book available through Primeros Libros at http://www.primeroslibros.org/

browse.html. Page 36 contains the drawing of K8, page 57 contains a drawing of K4,4

e.

Remark 7 (Drawing Crossings). How do we draw a crossing? The most common way is

to simply let the curves representing the edges cross, preferably at a large angle (RAC

drawings require right angles); alternatively one can draw crossings as bridges or by using

edge casing; see Edges and switches, tunnels and bridges by Eppstein, van Kreveld,

Mumford and Speckmann [173]. There may be more options in alternative styles; for

example, if vertices are represented by disks and edges as ribbons with boundary, then

crossings can be visualized by ribbons passing above or below each other, see for example

the 16th century drawing of K12 in [310, Figure 6] which has both vertex and edge labels

(illustrating a modal square of opposition). Alonso de la Vera Cruz uses an interesting

twist to visualize K8 (in his 1554 Recognitio Summularum, again for a square of oppo-

sition). He not only has ribbons passing above and below each other, but also through

(cid:7)

each other, see Figure 3; for background on the book, see [95].

Most of the research on crossing numbers seems to have been done in English, but

there are terms for crossings and crossing numbers in other languages. In German there is

the electronic journal of combinatorics (2017), #DS21

11

Kreuzung, Schnitt and Doppelpunkt for crossing and Kreuzungszahl for crossing number.13

In French, we have points dintersection [465] and croisement for crossings14 and nombres

de croisement for crossing number. In Italian there is incrocio for crossing and numero

dincrocio for crossing number.

2.1 A General Notion of Crossing Number

There are (at least) three main dimensions which inuence the specic notion of crossing

number one ends up with: the drawing style, the method of counting, and the mode of

representation. Within each dimension multiple decisions can be made, both global and

local. Global decisions in the drawing style include: underlying surface, straight-line

edges, monotone edges, local decisions include: no three edges sharing the same interior

point, no edge passing through a vertex; for method of counting, again we have global

decisions such as: do we count crossings between adjacent edges or edges that cross evenly

1 (depending on orientation), etc.; mode of

and local decisions: each crossing counts 1 or

representation is typically global; in the standard mode a curve carries exactly one edge,

but there are alternative models like conuent graph drawing and simultaneous graph

drawing in which a curve can carry more than one edge.

Many of these decisions have rarely been made explicitly; they were either assumed

implicitly or not considered at all. Even as one surveys the surprisingly large collection

of dierent crossing number variants that exist, one often nds that they dier from the

standard crossing number in at most one of the three dimensions (although there are some

exceptions such as the local toroidal crossing number, the book edge crossing number, or

the monotone independent odd crossing number).

Within this framework we can attempt a general denition of a crossing number :

given a graph G consider a particular drawing D representing G (via some mode of

representation). Assign to each crossing in D a value (typically 1, but could be

1, e.g.

for algebraic crossing number; values in Q, C or some group may be interesting). Now

calculate the crossing number (e, f ) for each pair of edges.15 This is typically done as the

sum (or absolute sum) of the values of the crossings shared by e and f .16 Finally, (D)

is calculated by combining all the values of (e, f ), typically by summing them up (over

all unordered pairs). Then (G) is the minimum (sometimes maximum) over all (D)

where D is an admissible drawing (depending on the drawing style) that represents G.

This generic denition of crossing number describes nearly all crossing number variants

reviewed in this paper. In any case, we are trying to be descriptive, not prescriptive.

13Steinitz [440] uses the term Doppelpunkt; it stems from the algebraic tradition and is now used for

crossings in knots. Schnittzahl typically means intersection number from algebraic geometry rather than

crossing number.

14Leclerc and Monjardet [316] use points non signiants (as opposed to the points representing vertices).

15One can also dene the crossing number by counting crossings along each edge (and dividing the

total by 2) but pairwise counting is the standard. This would seem to exclude some variants, like the

local crossing number or the triple crossing number, but see the discussion in Example 8.

16One could consider multiplication or maximization instead of addition.

the electronic journal of combinatorics (2017), #DS21

12

Example 8. Let us check some of the crossing number variants to test the bounds of our

general crossing number notion. For denitions, see the compendium.

Natural ts. The degenerate crossing number ts the general denition above: a cross-

ing shared by k edges is weighted as 1/(cid:0)k

2(cid:1). Independent crossing numbers can be

captured by assigning values of 0 to crossings between adjacent edges. The Rule

+ variants introduced by Pach and T th [368] are captured in the drawing style:

adjacent edges are not allowed to cross (alternatively, we could assign a value of

to each adjacent crossing). The triple crossing number (in which all crossings have

to be triple crossings) can be captured by pairwise counts (each triple crossings gives

three double crossings; since only triple crossings are allowed we can divide by 3 to

get the triple crossing...