Crossing Number Calculator

K₈, eight points all joined to each other. It has 8 × 7 / 2 = 28 edges. Hill’s formula takes four floors: ⌊8/2⌋ = 4, ⌊7/2⌋ = 3, ⌊6/2⌋ = 3, ⌊5/2⌋ = 2. Then cr(K₈) = ¼ × 4 × 3 × 3 × 2 = 72 / 4 = 18.

K_5,5, five kilns and five storage yards. Each side gives ⌊5/2⌋ × ⌊4/2⌋ = 2 × 2 = 4, so cr(K_5,5) = 4 × 4 = 16, with 25 edges.

The common mistakes. Dropping the floors turns the formula into n(n−1)(n−2)(n−3)/64, which for K₇ gives 840 / 64 = 13.125 instead of the true 9 (¼ × 3 × 3 × 2 × 2). And drawing the points on a circle with straight lines, the obvious picture, is far from optimal: every 4 points give one crossing, so K₈ drawn that way has C(8,4) = 70 crossings, not 18.

The brick factory. Pál Turán posed the bipartite problem from his own experience: in forced labour at a brick factory near Budapest in 1944, wagons ran on rails from every kiln to every storage yard, and they were hardest to push where the rails crossed. He told the story in “A note of welcome” in the first issue of the Journal of Graph Theory (1977). Asking for the fewest crossings is asking for the crossing number of K_m,n.

Zarankiewicz’s drawing and the gap. Kazimierz Zarankiewicz (Fundamenta Mathematicae 41, 1954), and independently Kazimierz Urbanik, put the m vertices on the x-axis and the n vertices on the y-axis, split as evenly as possible either side of the origin, and joined them with straight lines. That drawing has exactly Z(m, n) crossings, and it is the drawing on this page. Both also published proofs that nothing better is possible, but the proofs had an error that Gerhard Ringel and Paul Kainen found in the mid-1960s; Richard Guy told the story in “The decline and fall of Zarankiewicz’s theorem” (1969). From then on, Z(m, n) was a conjecture.

The complete graph. Frank Harary and Anthony Hill (1963) described Hill’s drawing of K_n and conjectured that its count, H(n), is the minimum; Richard Guy had published the same upper bound in 1960. Drawings with all vertices on one line and every edge above or below it (two-page drawings) also reach H(n). The one drawn here puts vertices 0 to n−1 on a line and draws edge {i, j} above the line when (i + j) mod n is less than n/2, below otherwise; the script counts its crossings each time and checks the total against H(n).

Cases proved before 2026. Daniel Kleitman (1970) proved Zarankiewicz’s formula whenever the smaller side has at most 6 vertices. Douglas Woodall (1993), using computer searches, extended it to a smaller side of 7 or 8 when the other side has at most 10 vertices. Shengjun Pan and Bruce Richter (2007) proved cr(K₁₁) = 100 with computer help, which gives cr(K₁₂) = 150, so Hill’s formula was known for every n ≤ 12. For K₁₃, Schaefer’s 2026 survey lists the value only as one of 219, 221, 223 or 225; Oswin Aichholzer reported a computer-assisted proof of 225 (and 315 for K₁₄) at a 2021 conference. For large n the best general lower bound was just over 98.5% of H(n).

New in 2026. On 23 September 2026 OpenAI published two AI-generated preprints, “The crossing number of complete graphs” and “The crossing number of complete bipartite graphs” (result family #165 in its openai/math repository), that claim both formulas for every size. Its Lean scope note says the formalization proves cr(K_n) = H(n) for every n ≥ 3, with a lower bound and a matching two-page drawing, and cr(K_m,n) = Z(m, n) for all positive m and n, counting crossings as points in the plane, so two edges that cross twice count twice. In other words, it is proved in a 2026 AI-generated preprint with a machine-checked Lean proof (published with Lean Comparator checks), and it has not yet been peer reviewed. What a Lean check does and does not establish is explained in what “Lean-checked” means. This calculator labels sizes settled before 2026 as proven (classical) and the rest as proven in 2026 (AI-generated, Lean-checked).

Straight lines are not always enough. If every edge must be a straight segment, K_n can need more: 19 for K₈, 62 for K₁₀, 102 for K₁₁ and 153 for K₁₂, against 18, 60, 100 and 150 with curves (at n = 9 both are 36). That is why the K_n drawing here uses arcs. Zarankiewicz’s K_m,n drawing is straight already.

Sources

• OpenAI, Lean scope note for result 165, “The Harary–Hill and Zarankiewicz crossing-number formulas”, and the preprints The crossing number of complete graphs and The crossing number of complete bipartite graphs (23 September 2026; not peer reviewed).
• Marcus Schaefer, The Graph Crossing Number and its Variants: A Survey, Electronic Journal of Combinatorics, Dynamic Survey DS21, ninth edition (17 July 2026): the status of both conjectures, Kleitman, Woodall, Pan–Richter, the K₁₃ range and the history of the gap in Zarankiewicz’s proof.
• P. Turán, A note of welcome, Journal of Graph Theory 1 (1977) 7–9, doi:10.1002/jgt.3190010105.
• K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fundamenta Mathematicae 41 (1954) 137–145, doi:10.4064/fm-41-1-137-145.
• R. K. Guy, The decline and fall of Zarankiewicz’s theorem, in Proof Techniques in Graph Theory, Academic Press (1969) 63–69.
• F. Harary and A. Hill, On the number of crossings in a complete graph, Proceedings of the Edinburgh Mathematical Society 13 (1963) 333–338, doi:10.1017/S0013091500025645.
• D. J. Kleitman, The crossing number of K_5,n, Journal of Combinatorial Theory 9 (1970) 315–323, doi:10.1016/S0021-9800(70)80087-4.
• D. R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture, Journal of Graph Theory 17 (1993) 657–671, doi:10.1002/jgt.3190170602.
• S. Pan and R. B. Richter, The crossing number of K₁₁ is 100, Journal of Graph Theory 56 (2007) 128–134, doi:10.1002/jgt.20249.
• B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos and G. Salazar, The 2-page crossing number of K_n, Discrete & Computational Geometry 49 (2013) 747–777, doi:10.1007/s00454-013-9514-0.
• OEIS A014540, rectilinear (straight-line) crossing number of K_n.

This calculator gives the crossing number of the complete graph K_n and the complete bipartite graph K_m,n: the fewest pairs of edges that must cross when the graph is drawn on a flat sheet. It uses exact integer arithmetic, so K_1,000,000 comes out to the last digit (about 1.56 × 10²²) rather than rounded.

It does not only quote the formula. For small sizes it draws a layout that reaches the minimum, marks every crossing, counts them with an exact geometric test and shows whether the count matches. It also says which sizes were proved by classical methods and which rest on the 2026 proof.

All calculations run in your browser; nothing you enter is sent to a server.

It is meant for students and teachers of graph theory, puzzle fans looking at the utilities problem, and anyone laying out wiring or network diagrams who wants to know how many crossings cannot be avoided.

Related calculators: Graph Algorithm Laboratory, Permutation and Combination Calculator, and Big Number Calculator.