董晓媛，马登举

(1.南通师范高等专科学校数理系，江苏 南通 226007；2.南通大学理学院，江苏 南通 226000)

1 预备知识

研究交叉数的主要动机之一是图的交叉数在超大规模集成电路设计中的应用.国内外许多学者都研究过图的交叉数问题，但是到目前为止还没有找到能确定任意图的交叉数的算法.

图的一个平面画法是将图的顶点用平面上的不同点表示，边用简单曲线段表示，使得表示每条边的曲线不经过除他们的端点外的其他点.同时，还要求一个图的画法满足下列条件：(1)相邻的两条边不交叉；(2)两条边相交叉不多于一次；(3)两条边不相切；(4)没有3条边交于同一个顶点.在图G的所有画法中，交叉点数最少的画法所含的交叉点的数目称为图G的交叉数，记为cr(G).

一个k页书是由一条直线l和k≥1个半平面组成，使得每个半平面的边界都是直线l.将每个半平面称为页，而直线l称为书脊.一个图G在一个k页书上的画法是指将这个图的每个顶点都位于书脊上，每条边都画在同一页上.图G在一个k页书上的所有画法的交叉点数最少的画法所含的交叉点的数目称为图G的2页交叉数，记为cr2(G).由于一个2页书就可以形成一个平面，容易得到cr(G)≤cr2(G).

1987年，Chung等[1]对一类书图进行了研究.众所周知，一本书是由一个书脊和k个书页组成的，这k个书页有一个共同的边界就是书脊.把一个图嵌入到这本书中，这个图的每个顶点都位于书脊上，每条边都位于同一页上.最近，书图已经得到了广泛……