Why a wartime brick factory problem still haunts modern computer chip design
In short: During World War II, mathematician Pál Turán noticed that tracks crossing in a brick factory made wagons harder to push. This observation birthed the crossing number, a fundamental graph theory problem. Today, this concept is vital for VLSI design, helping engineers minimize intersections in complex, high-density electronic circuits.
The crossing number of a graph is defined as the minimum number of edge intersections possible when drawing that graph on a flat plane. If a graph can be drawn with zero crossings, it is considered planar. While this sounds simple, determining the crossing number for most graph families is notoriously difficult. In 1983, researchers Garey and Johnson proved that calculating the crossing number is an NP-hard problem, meaning it remains computationally challenging even for relatively simple structures like cubic or near-planar graphs.
The problem's origins are rooted in Pál Turán's practical experience in a wartime brick factory, where he sought to minimize track intersections between kilns and storage sites. Mathematically, this is equivalent to finding the crossing number of a complete bipartite graph. Despite decades of study, Turán's original formula for these graphs remains a conjecture. Similarly, a formula for complete graphs, first published by Richard K. Guy in 1960 based on work by artists Anthony Hill and John Ernest, remains unproven for larger graphs, though it has been verified for small cases.
Beyond pure mathematics, the crossing number has profound practical applications. The 'crossing number inequality'—which states that for sufficiently dense graphs, the number of crossings grows proportionally to the cube of the edges divided by the square of the vertices—is a cornerstone of VLSI design. By minimizing crossings, engineers can optimize the physical layout of integrated circuits. Furthermore, this inequality has provided elegant proofs for major theorems in incidence geometry, such as the Szemerédi-Trotter theorem, demonstrating how a simple question about factory tracks evolved into a powerful tool for modern science.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Crossing number (graph theory)
To cite this card, link to https://intellectplus.co.uk/app/science-crossing-number-graph-theory.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?