交叉數 在圖論交叉數 cr  G  displaystyle textcrG 是將圖 G displaystyle G 畫在平面上時邊的交叉點的最小數目若 cr  G    displaystyle hboxcrG 則 G displaystyle G 稱為平面圖在圖形製圖英语graph drawing方面計算圖的交叉數仍是一個重要問題因為讀者研究發現畫圖的交叉越少越有利於讀者理解 交叉數的研究始於圖蘭磚廠問題英语Turáns brick factory problem圖蘭帕爾想求磚廠中將每個窯爐各與全部貨倉用路軌連接的最優方案使路軌的交叉儘可能少按上述定義即是問完全二部圖的交叉數同一問題約莫同時在社會學研究提出因為事關社會關係圖英语sociogram的繪製 圖蘭猜想了完全二部圖交叉數的公式但該公式迄今未獲證完全圖的交叉數公式亦然 交叉數不等式斷言若邊數 e displaystyle e 与頂點數 n displaystyle n 的比值大于某个常数則交叉數不小于 e   n  displaystyle en 乘以另一个固定的常数此結論在超大规模集成电路設計與組合幾何方面有應用 如無特別註明交叉數允許使用任意曲線來畫邊另一個相關概念是直線交叉數其要求僅使用直線段來畫邊所以未必等於交叉數更具體說完全圖 K n displaystyle Kn 的直線交叉數就是平面上處於一般位置的 n displaystyle n 個點所能組成的凸四邊形的最少數目因為每個凸四邊形的兩條對角線產生一個交叉直線交叉數問題與幸福結局問題密切相關 給定一個圖計算其交叉數是一個NP難問題