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

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