圖交叉數

給定一個“好的”圖 (即，一個所有相交圖邊在一個點相交，並由四個不同的圖頂點產生的圖)，交叉數是圖可以繪製的最小可能交叉次數，包括使用彎曲（非直線）邊。文獻中存在幾種符號約定，其中一些更常見的符號是 (例如，Pan 和 Richter 2007; Clancy et al. 2019), , (例如，Pach 和 Tóth 2005), 和 。

交叉數為 0 的圖被稱為平面圖。對於圖交叉數為 1 的圖，似乎沒有標準使用的術語。特別是，術語“幾乎平面”和“1-平面”在文獻中用於其他概念。因此，在這項工作中，術語單交叉圖將用於交叉數為 1 的圖。交叉數為 2 的圖被稱為雙交叉圖。這些術語總結在下表中。

Garey 和 Johnson (1983ab) 表明，確定交叉數是一個 NP-完全問題。Buchheim et al. (2008) 使用整數線性規劃來制定第一個精確演算法，以找到可證明的最佳交叉數。Chimani et al. 隨後給出了一個整數線性規劃公式，該公式在交叉數高達 37 時可以實際有效，該公式試圖透過基於 Buchheim et al. (2008)、Chimani et al. 和作者相關工作的分支定界定價來確定性地找到交叉數。作者提供了一個 Web 表單，請求將此演算法應用於提交的圖 (Chimani 和 Wiedera)。相比之下，Haythorpe 和同事實現了一種稱為 QuickCross 的快速啟發式演算法，旨在找到圖的最優或接近最優的嵌入，如 Clancy et al. (2018) 所討論的，並且可供下載。

雖然圖交叉數允許具有任意形狀邊（例如，曲線）的圖嵌入，但直線交叉數 是直線嵌入圖中交叉的最小可能數量。當（非直線）圖交叉數滿足 時, (Bienstock 和 Dean 1993)。雖然 Bienstock 和 Dean 實際上並沒有證明 的情況，但他們表示可以類似於 的情況建立。該結果不能擴充套件到 ，因為存在圖 使得 但 對於任何 。

成立的最小簡單圖出現在 8 個節點上。下表總結了四個這樣的例子。上面說明了 16-胞圖和完全圖 (Harary 和 Hill 1962-1963) 的最小交叉和直線交叉嵌入。

圖
16-胞圖	6	8
-圖蘭圖	9	10
8-雙環面圖 8	9	10
完全圖	18	19

Ajtai et al. (1982) 表明存在一個絕對常數 使得

對於每個具有頂點數 和邊數 的圖。Ajtai et al. (1982) 確定不等式對於 成立，隨後改進為 1/64 (參見 Clancy et al. 2019)。

蓋伊猜想提出了完全圖 的交叉數的閉合形式，扎蘭凱維奇猜想提出了完全二分圖 的交叉數的閉合形式。還提出了 環面網格圖 的交叉數的猜想閉合形式。