路径幂图的交叉数、算法与应用研究

图的交叉数在CAD中有广泛的应用，如草图的识别与重画、电路板设计等。它是NP困难问题，研究它对解决一般NP困难问题很有意义。.到目前为止，只有很有限的一些图族的交叉数得到了精确值，其成果主要集中在对完全图，完全二分图及部分正则图的研究。但实际应用中遇到的图更多的是非正则图。本课题着重研究一类非正则图- - 路径幂图的交叉数；同时，研制出较好的计算图的交叉数的算法与计算图的交叉数的上界的算法, 为图的交叉数的实际应用提供更坚实的理论基础。.在图的交叉数问题研究领域，申请者已取得了部分国际领先成果，本项目的研究，将有助于我们在该领域继续保持国际领先水平。