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