What is "the crossing number inequality"?

Question

Could someone explain to me what "The crossing number inequality" is? How is it different from the crossing number of a graph?

Answer 1

The crossing number is an invariant of a graph describing how far away from being planar the graph is. A graph is planar if and only if its crossing number is zero. A graph which always has at least one set of edges crossing when drawn in the plane has crossing number at least one, and so on.

The crossing number inequality is a lower bound on the crossing number which can be computed from easier observations, namely the number of vertices and edges. The crossing number itself can be hard to compute for large graphs, but if you don't need to know it exactly for a particular application then having a lower bound can be quite useful, especially if it's easy to compute.

Specifically, the crossing number is always greater than $e^3 / (29n^2)$ for a graph with $e$ edges and $n$ vertices where $e > 7n$.

Answer 2

If a graph $G$ is dense enough, then we can guarantee the crossing number is at least a certain value.

Let $e$ be the number of edges in a graph $G$ of order $n$ with $e\ge 4n$, then $\operatorname{cr}(G)\ge\frac{e^3}{64n^2}$.