环面交叉数

图 的环面交叉数 是图 在环面上绘制时所需的最小交叉数。

平面图的环面交叉数为 0，环面交叉数为 0 的非平面图称为环面图。环面交叉数为 0 的非平面图的图亏格为 1，因为它可以在环面上嵌入（但不能在平面上嵌入），且没有交叉。

图交叉数 Graph Crossing Number 或直线交叉数 Rectilinear Crossing Number 小于 2 的图的环面交叉数为 0。更一般地，移除单条边后变为平面图的图（换句话说，图的偏斜度 的图 ）也具有环面交叉数 0。然而，存在环面交叉数 的图，其所有移除单边子图都是非平面图，因此这个条件是充分的但不是必要的。

如果一个有 条边的图 的环面交叉数 ，那么 (Pach and Tóth 2005)，其中 表示二项式系数。此外，如果 是一个有 个顶点，最大顶点度 的图，且其环面交叉数 ，那么

(1)

其中 是一个正常数 (Pach and Tóth 2005)。

完全图 对于 , 2, ... 的环面交叉数是 0, 0, 0, 0, 0, 0, 0, 4, 9, 23, 42, 70, 105, 154, 226, 326, ... (OEIS A014543)。

在环面上的交叉数由下式给出

(2)

(Guy and Jenkyns 1969, Ho 2005)。因此，对于 , 2, ... 的前几个值是 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, ... (OEIS A008724)。

在环面上的交叉数由下式给出

(3)

(Ho 2009)。因此，对于 , 2, ... 的前几个值是 0, 0, 0, 0, 2, 4, 6, 8, 12, 16, 20, 24, 30, 36, ... (OEIS A182568)。有趣的是，相同的结果也适用于 、、 和 。

完全二分图 的环面交叉数总结在下表中。

	1	2	3	4	5	6
1	0	0	0	0	0	0
2		0	0	0	0	0
3			0	0	0	0
4				0	2	4
5					5	8
6						12