带限制条件的两个平面图同时嵌入的交叉数

作者：卢俊杰; 任韩

来源：华东师范大学学报(自然科学版), 2009, (01): 7-12.

• 平面图
• 交叉数
• 划分
• 边连通度 planar graph
• crossing number
• partition
• edge-connectivity

考虑两个平面图,一个染成红色,另一个染成绿色.两个图同时2-胞腔嵌入平面时,在一定的限制条件下,红色的边与绿色的边会相交.称这样的交点为交叉点.在所有的嵌入方式中交叉点的最小个数称为交叉数.本文利用图的划分和最小边割集,把这种交叉数问题转化为一类整数规划问题,得出了一些结果.

• 出版日期2009
• 单位华东理工大学; 华东师范大学; 上海交通大学