图交叉数

给定一个“好的”图 (即，一个所有相交图边在一个点相交，并由四个不同的图顶点产生的图)，交叉数是图可以绘制的最小可能交叉次数，包括使用弯曲（非直线）边。文献中存在几种符号约定，其中一些更常见的符号是 (例如，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)。

盖伊猜想提出了完全图 的交叉数的闭合形式，扎兰凯维奇猜想提出了完全二分图 的交叉数的闭合形式。还提出了 环面网格图 的交叉数的猜想闭合形式。