Crossing number

In mathematics, crossing numbers arise in two related contexts: in knot theory and in graph theory.

Contents

1 Crossing numbers in knot theory 2 Crossing numbers in graph theory 2.1 Complexity 2.2 The crossing number inequality 2.2.1 Proof of crossing number inequality 3 References

Crossing numbers in knot theory

In knot theory, the crossing number is an example of a knot invariant. A knot's crossing number is simply the lowest number of crossings of any diagram of the knot.

By way of example, the unknot has crossing number zero, the trefoil knot three and the figure-eight knot four. There are no other knots with a crossing number this low and just two knots have crossing number 5, but the number of knots with a particular crossing number increases rapidly as we go higher.

Tables of prime knots are traditionally indexed by crossing number, with a subscript to indicate which particular knot out of those with this many crossings is meant (this sub-ordering is not based on anything in particular, except that torus knots are listed first). The listing goes 3₁ (the trefoil knot), 4₁ (the figure-eight knot), 5₁, 5₂, 6₁, etc. This order has not changed significantly since P. G. Tait published a tabulation of knots in 1877.

Crossing numbers in graph theory

The crossing number cr(G) of a graph G is the lowest number of crossings of a planar diagram of the graph G. For instance, a graph is planar if and only if its crossing number is zero.

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. In fact, Petr Hliněný showed in 2003 that the problem remains NP-hard even when restricted to cubic graphs, which have low degree.

On the positive side, there is an efficient (O(|V|²)) algorithm for determining if the crossing number is less than a fixed constant k; it remains difficult for larger k, such as |V|/2. There are also efficient approximation algorithms for computing the crossing number of graphs of bounded degree. 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.

The crossing number inequality

The very useful crossing number inequality, discovered independently by Ajtai, Chvatal, Newborn, and Szemerédi [1] and by Leighton [2], asserts that if a graph G (undirected, with no loops or multiple edges) with n vertices and e edges has many edges, in the sense that if

<math>e > 7.5 n,\,<math>

then we have

<math>\operatorname{cr}(G) \geq \frac{e^3}{33.75 n^2}.\,<math>

The constant 33.75 is the best known to date, and is due to Pach and Tóth [3]; the constant 7.5 can be lowered to 4, but at the expense of replacing 33.75 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 [4] 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.

Proof of crossing number inequality

We first give a preliminary estimate: for any graph G with n vertices and e edges, we have

<math>\operatorname{cr}(G) \geq e - 3n.\,<math>

To prove this, consider a diagram of G which has exactly cr(G) crossings. Each of these crossings can be removed by removing an edge from G. Thus we can find a graph with at least <math>e-\operatorname{cr}(G)<math> edges and n vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have <math>e-\operatorname{cr}(G) \leq 3n<math>, and the claim follows. (In fact we have <math>e-\operatorname{cr}(G) \leq 3n-6<math> 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 H of G by allowing each vertex of G to lie in H independently with probability p, and allowing an edge of G to lie in H if and only if its two vertices were chosen to lie in H. Let <math>e_H<math> denote the number of edges of H, and let <math>n_H<math> denote the number of vertices.

Now consider a diagram of G 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 G.

Since H is a subgraph of G, this diagram contains a diagram of H; let <math>\operatorname{cr}_H<math> denote the number of crossings of this random graph. By the preliminary crossing number inequality, we have

<math> \operatorname{cr}_H \geq e_H - 3n_H.<math>

Taking expectations we obtain

<math>{\Bbb E}(\operatorname{cr}_H) \geq {\Bbb E(e_H)} - 3 {\Bbb E}(n_H).<math>

Since each of the n vertices in G had a probability p of being in H, we have <math>{\Bbb E}(n_H) = pn<math>. Similarly, since each of the edges in G has a probability <math>p^2<math> of remaining in H (since both endpoints need to stay in H), then <math>{\Bbb E}(e_H) = p^2 e<math>. Finally, every crossing in the diagram of G has a probability <math>p^4<math> of remaining in H, since every crossing involves four vertices, and so <math>{\Bbb E}(\operatorname{cr}_H) = p^4 \operatorname{cr}(G)<math>. Thus we have

<math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.\,<math>

If we now set p to equal 4n/e (which is less than one, since we assume that e is greater than 4n), we obtain after some algebra

<math> \operatorname{cr}(G) \geq e^3 / 64 n.\,<math>

A slight refinement of this argument allows one to replace 64 by 33.75 when e is greater than 7.5 n; see [3].

References

1. M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi, Crossing-free subgraphs, Annals of Discrete Mathematics 12 (1982), 9-12.
2. T. Leighton, Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, MA, 1983.
3. J. Pach and G. Tóth: Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427-439.
4. L. A. Székely: Crossing numbers and hard Erdos problems in discrete geometry, Combinatorics, Probability and Computing 6 (1997), 353-358.
5. M.R. Garey and D.S. Johnson. Crossing Number is NP-Complete. SIAM J. Alg. Discr. Meth. 4, p.312-316. 1983.
6. Petr Hliněný. Crossing Number Is Hard for Cubic Graphs (http://kam.mff.cuni.cz/~hlineny/papers/crcubic2-mfcs.pdf). MFCS 2004: 772-782. 2003.