华东师范大学学报(自然科学版) ›› 2009, Vol. 2009 ›› Issue (1): 7-12.

• 应用数学与基础数学 • 上一篇    下一篇

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

卢俊杰1, 任 韩2   

  1. 1.上海交通大学 数学系, 上海 200062; 2.华东师范大学 数学系, 上海 241000
  • 收稿日期:2008-03-01 修回日期:2008-05-13 出版日期:2009-01-25 发布日期:2009-01-25
  • 通讯作者: 卢俊杰

Crossing number of simultaneous embedding of two planar graphs with restriction (Chinsese)

LU Jun-jie1, REN Han2   

  1. 1. Department of Mathematics, Shanghai jiaotong University, Shanghai 200062, China; 2.Department of Mathematics, East China Normal University, Shanghai 200062, China
  • Received:2008-03-01 Revised:2008-05-13 Online:2009-01-25 Published:2009-01-25
  • Contact: LU Jun-jie

PDF

1527

摘要：

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

关键词: 平面图, 交叉数, 划分, 边连通度, 平面图, 交叉数, 划分, 边连通度

Abstract: Consider a red planar graph and a green planar graph
simutaneously $2$-cell embedded on a surface. With some restriction,
a red edge can cross a green edge. This paper studied the minimum
number of these red-green crosses by using technique of integer
programming, and some results are obtained.

Key words: crossing number, partition, edge-connectivity, planar graph, crossing number, partition, edge-connectivity

中图分类号: