In the mathematics of graph drawing, the crossing number inequality, also called the crossing lemma, gives a lower bound on the smallest possible number of edge crossings in a plane drawing of a given graph, expressed as a function of the graph's own numbers of edges and vertices. It states that once the number of edges is large enough relative to the number of vertices, the crossing number is at least proportional to the cube of the edge count divided by the square of the vertex count. The inequality was discovered independently by Ajtai, Chvatal, Newborn and Szemeredi and by Leighton, and it's applied in VLSI circuit design and in combinatorial geometry.
Facts
StatementThe crossing number inequality states that for a graph G with n vertices and e edges where e is greater than 7n, the crossing number of G, the minimum number of edge crossings over any plane drawing, is at least e cubed divided by 29 times n squared. 1 Proof YearDiscovered independently by Ajtai, Chvatal, Newborn and Szemeredi and by F. Thomson Leighton; the reference list gives 1982 for the Ajtai-Chvatal-Newborn-Szemeredi paper. Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
Proved By
Source Crossing Number Inequality (Wikipedia)
Sources
1. Crossing Number Inequality (Wikipedia)
Wikimedia FoundationLede
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.
References list
Ajtai, M.; Chvatal, V.; Newborn, M. M.; Szemeredi, E. (1982), Crossing-free subgraphs
Lead section, statement-form reference
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.
Proved By: Endre Szemeredi, Lead paragraph
and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.