The Electronic Journal of Combinatorics · 2001 · 20 citations · 18 references
Natural SciencesMathematicsCombinatoricsComputational GeometryGeometryCombinatorial EnumerationCombinatorial Number TheoryEnumerative CombinatoricsGeometric GraphsGraph DrawingGraph TheoryCrossing Number
The rectilinear crossing number of a graph $G$ is the minimum number of edge crossings that can occur in any drawing of $G$ in which the edges are straight line segments and no three vertices are collinear. This number has been known for $G=K_n$ if $n \leq 9$. Using a combinatorial argument we show that for $n=10$ the number is 62.
18
de Ng Dick Bruijn · Data Archiving and Networked Services (DANS) · 1946 · 1.3K citations · Full text
Crossing Number is NP-Complete
M. R. Garey, David S. Johnson · SIAM Journal on Algebraic and Discrete Methods · 1983 · 669 citations
Daniel J. Kleitman · Journal of Combinatorial Theory · 1970 · 187 citations
New lower bound techniques for VLSI
Frank Thomson Leighton · Theory of Computing Systems · 1984 · 179 citations