Crossing number (graph theory)

A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3.

In graph theory, the crossing number cr(G) of a graph Template:Mvar is the lowest number of edge crossings of a plane drawing of the graph Template:Mvar. For instance, a graph is planar if and only if its crossing number is zero.

The mathematical origin of the study of crossing numbers is in Turán's brick factory problem, in which Pál Turán asked to determine the crossing number of the complete bipartite graph Template:Mvar.[1] However, the same problem of minimizing crossings was also considered in sociology at approximately the same time as Turán, in connection with the construction of sociograms.[2] It continues to be of great importance in graph drawing.

Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves; the rectilinear crossing number requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of Template:Mvar points in general position, closely related to the Happy Ending problem.[3]

History

During World War II, Hungarian mathematician Pál Turán was forced to work in a brick factory, pushing wagon loads of bricks from kilns to storage sites. The factory had tracks from each kiln to each storage site, and the wagons were harder to push at the points where tracks crossed each other, from which Turán was led to ask his brick factory problem: what is the minimum possible number of crossings in a drawing of a complete bipartite graph?[4]

Zarankiewicz attempted to solve Turán's brick factory problem;[5] his proof contained an error, but he established a valid upper bound of

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }$

for the crossing number of the complete bipartite graph Template:Mvar. The conjecture that this inequality is actually an equality is now known as Zarankiewicz' crossing number conjecture. The gap in the proof of the lower bound was not discovered until eleven years after publication, nearly simultaneously by Gerhard Ringel and Paul Kainen; see [6]

The problem of determining the crossing number of the complete graph was first posed by Anthony Hill, and appears in print in 1960.[7] Hill and his collaborator John Ernest were two constructionist artists fascinated by mathematics, who not only formulated this problem but also originated a conjectural upper bound for this crossing number, which Richard K. Guy published in 1960.[7] Namely, the conjecture is that

${\displaystyle {\textrm {cr}}(K_{p})\leq {\tfrac {1}{4}}\left\lfloor {\tfrac {p}{2}}\right\rfloor \left\lfloor {\tfrac {p-1}{2}}\right\rfloor \left\lfloor {\tfrac {p-2}{2}}\right\rfloor \left\lfloor {\tfrac {p-3}{2}}\right\rfloor ,}$

which gives values of 1, 3, 9, 18, 36, 60, 100, 150 for p = 5, ..., 12; see sequence (A000241) in the OEIS. An independent formulation of the conjecture was made by Thomas L. Saaty in 1964.[8] Saaty further verified that the upper bound is achieved for p ≤ 10 and Pan and Richter showed that it also is achieved for p = 11, 12.

If only straight-line segments are permitted, then one needs more crossings. The rectilinear crossing numbers for K5 through K12 are 1, 3, 9, 19, 36, 62, 102, 153, (A014540) and values up to K27 are known, with K28 requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.[9] Interestingly, it is not known whether the ordinary and rectilinear crossing numbers are the same for bipartite complete graphs. If the Zarankiewicz conjecture is correct, then the formula for the crossing number of the complete graph is asymptotically correct;[10] that is,

${\displaystyle \lim _{p\to \infty }{\textrm {cr}}(K_{p}){\tfrac {64}{p^{4}}}=1.}$

As of January 2012, crossing numbers are known for very few graph families. In particular, except for a few initial cases, the crossing number of complete graphs, bipartite complete graphs, and products of cycles all remain unknown. There has been some progress on lower bounds, as reported by Template:Harvtxt.[11]

The Albertson conjecture, formulated by Michael O. Albertson in 2007, states that, among all graphs with chromatic number Template:Mvar, the complete graph Template:Mvar has the minimum number of crossings. That is, if the Guy-Saaty conjecture on the crossing number of the complete graph is valid, every Template:Mvar-chromatic graph has crossing number at least equal to the formula in the conjecture. It is now known to hold for n ≤ 16.[12]

Complexity

In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem.[13] In fact the problem remains NP-hard even when restricted to cubic graphs[14] and to near-planar graphs[15] (graphs that become planar after removal of a single edge). More specifically, determining the rectilinear crossing number is complete for the existential theory of the reals.[16]

On the positive side, there are efficient algorithms for determining if the crossing number is less than a fixed constant Template:Mvar — in other words, the problem is fixed-parameter tractable.[17] It remains difficult for larger k, such as |V|/2. There are also efficient approximation algorithms for approximating cr(G) on graphs of bounded degree.[18] In practice heuristic algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number[19] distributed computing project.

Crossing numbers of cubic graphs

The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in OEIS). The smallest 1-crossing cubic graph is the complete bipartite graph K3,3, with 6 vertices. The smallest 2-crossing cubic graph is the Petersen graph, with 10 vertices. The smallest 3-crossing cubic graph is the Heawood graph, with 14 vertices. The smallest 4-crossing cubic graph is the Möbius-Kantor graph, with 16 vertices. The smallest 5-crossing cubic graph is the Pappus graph, with 18 vertices. The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices. None of the four 7-crossing cubic graphs, with 22 vertices, are well known.[20] The smallest 8-crossing cubic graphs include the Nauru graph and the McGee graph or (3,7)-cage graph, with 24 vertices.

In 2009, Exoo conjectured that the smallest cubic graph with crossing number 11 is the Coxeter graph, the smallest cubic graph with crossing number 13 is the Tutte–Coxeter graph and the smallest cubic graph with crossing number 170 is the Tutte 12-cage.[21][22]

The crossing number inequality

The very useful crossing number inequality, discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi[23] and by Leighton,[24] is as follows:

For an undirected simple graph Template:Mvar with Template:Mvar vertices and Template:Mvar edges such that e > 7n we have:
${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

The constant 29 is the best known to date, and is due to Ackerman;[25] the constant 7 can be lowered to 4, but at the expense of replacing 29 with the worse constant of 64.

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science. Later, Székely[26] also realized that this inequality yielded very simple proofs of some important theorems in incidence geometry, such as Beck's theorem and the Szemerédi-Trotter theorem, and Tamal Dey used it to prove upper bounds on geometric k-sets.[27]

For graphs with girth larger than 2r and e ≥ 4n, Pach, Spencer and Tóth[28] demonstrated an improvement of this inequality to

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$

Proof of crossing number inequality

We first give a preliminary estimate: for any graph Template:Mvar with Template:Mvar vertices and Template:Mvar edges, we have

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$

To prove this, consider a diagram of Template:Mvar which has exactly cr(G) crossings. Each of these crossings can be removed by removing an edge from Template:Mvar. Thus we can find a graph with at least e − cr(G) edges and Template:Mvar vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have e − cr(G) ≤ 3n, and the claim follows. (In fact we have e − cr(G) ≤ 3n − 6 for n ≥ 3).

To obtain the actual crossing number inequality, we now use a probabilistic argument. We let 0 < p < 1 be a probability parameter to be chosen later, and construct a random subgraph Template:Mvar of Template:Mvar by allowing each vertex of Template:Mvar to lie in Template:Mvar independently with probability Template:Mvar, and allowing an edge of Template:Mvar to lie in Template:Mvar if and only if its two vertices were chosen to lie in Template:Mvar. Let Template:Mvar and crH denote the number of edges, vertices and crossings of Template:Mvar, respectively. Since Template:Mvar is a subgraph of Template:Mvar, this diagram contains a diagram of Template:Mvar. By the preliminary crossing number inequality, we have

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$

Taking expectations we obtain

${\displaystyle \mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].}$

Since each of the Template:Mvar vertices in Template:Mvar had a probability Template:Mvar of being in Template:Mvar, we have E[nH] = pn. Similarly, each of the edges in Template:Mvar has a probability p2 of remaining in Template:Mvar since both endpoints need to stay in Template:Mvar, theerefore E[eH] = p2e. Finally, every crossing in the diagram of Template:Mvar has a probability p4 of remaining in Template:Mvar, since every crossing involves four vertices. To see this consider a diagram of Template:Mvar with cr(G) crossings. We may assume that any two edges in this diagram with a common vertex are disjoint, otherwise we could interchange the intersecting parts of the two edges and reduce the crossing number by one. Thus every crossing in this diagram involves four distinct vertices of Template:Mvar. Therefore E[crH] = p4cr(G) and we have

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$

Now if we set p = 4n/e < 1 (since we assumed that e > 4n), we obtain after some algebra

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$

A slight refinement of this argument allows one to replace 64 by 33.75 for e > 7.5n.[25]

Notes

1. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
2. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
3. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
4. {{#invoke:citation/CS1|citation |CitationClass=book }}
5. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
6. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
7. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
8. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
9. Template:Cite web
10. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
11. {{#invoke:Citation/CS1|citation |CitationClass=journal }}.
12. Template:Cite arXiv
13. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
14. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
15. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
16. {{#invoke:citation/CS1|citation |CitationClass=conference }}.
17. {{#invoke:Citation/CS1|citation |CitationClass=journal }}; {{#invoke:citation/CS1|citation |CitationClass=conference }}
18. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
19. Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
20. Template:Cite web
21. {{#invoke:Citation/CS1|citation |CitationClass=journal }}.
22. {{#invoke:citation/CS1|citation |CitationClass=conference }}
23. {{#invoke:citation/CS1|citation |CitationClass=book }}
24. {{#invoke:citation/CS1|citation |CitationClass=citation }}. For earlier results with worse constants see {{#invoke:citation/CS1|citation |CitationClass=citation }}; {{#invoke:citation/CS1|citation |CitationClass=citation }}.
25. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
26. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
27. {{#invoke:Citation/CS1|citation |CitationClass=journal }}