Crossing number inequality

In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2.

It has applications in VLSI design and combinatorial geometry, and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi[1] and by Leighton.[2]

  1. ^ Ajtai, M.; Chvátal, V.; Newborn, M. M.; Szemerédi, E. (1982), "Crossing-free subgraphs", Theory and practice of combinatorics, North-Holland Mathematics Studies, vol. 60, North-Holland, Amsterdam, pp. 9–12, MR 0806962.
  2. ^ Leighton, T. (1983), Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press.