关于图的交叉数问题研究

确定图的交叉数不仅有着重要的理论意义，而且有着较强的现实意义，如电子电路板的设计中的布线问题、CAD领域中的草图识别与重画问题等。然而,一般地，确定确定图的交叉数又是一个NP难问题。目前能够确定交叉数的图类非常少, 且大多集中在一些特殊的图类上。本项目一方面确定一些重要图类的交叉数, 如完全2-部图、完全多部图、以及一些笛卡尔积图等；同时也研究图的交叉数与图的结构、图的其它参数的内在联系和有关性质。研究3-正则图的交叉数的子图插值性，研究图类与其相关图类的交叉数之间的关系，发现和发展研究图的交叉数新方法。另外，我们也研究图在其它曲面(定向或不可定向)的交叉数性质,确定一些重要图类在这些曲面（非球面）上的交叉数。本项目的研究成果将极大地丰富图的交叉数理论，有力地推动图的交叉数研究发展，且带动相关学科的发展。