交叉数为2的笛卡尔积图

作者：王晶; 张作政^*

来源：运筹学学报, 2022, 26(04): 98-106.

DOI：10.15960/j.cnki.issn.1007-6093.2022.04.008

• 交叉数
• 画法
• 笛卡尔积图

图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G1为圈且cr(G1G2)-2时,因子图G1和G2满足的充要条件。在此基础上,本文研究当|V(G1)|≥3且cr(G1G2)=2时,G1和G2应满足的充要条件。

• 单位
  数学学院; 长沙学院