图类的亏格与嵌入分布及其相关问题研究

项目名称： 图类的亏格与嵌入分布及其相关问题研究

项目编号： No.11371133

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 黄元秋

作者单位： 湖南师范大学

项目金额： 62万元

中文摘要： 拓扑图论是图论学科的重要分支。确定图的亏格和嵌入分布均是NP-难问题，但又是拓扑图论中的经典和核心问题，引起了国际上许多知名学者的重视和研究。本项目既结合传统的方法，又运用刘彦佩提出的联树模型法以及发现新的组合方法，确定一些经典图类的亏格及嵌入分布；给出图在特定嵌入下的嵌入数目估计；借助代数学中的多项式理论与方法，研究图的嵌入多项式的根的分布性质；研究求一些特殊图类的亏格及嵌入分布的多项式时间算法；同时开展图的嵌入分布单峰猜想研究。项目研究的内容，有的是我们前期研究结果的深化和拓展（如最大亏格嵌入个数研究）,有的是经典问题（如确定图的亏格及嵌入分布），有的是国际重要学术刊物上提出的著名猜想或新问题（如Gross猜想、联图亏格扩展问题）。内容涉及到代数学、曲面拓扑学、群论、算法理论等领域。问题的解决，不仅极大地丰富和完善拓扑图论中的相关内容，同时也将有力地推动拓扑图论及促进相关学科的发展。

中文关键词： 图的亏格；嵌入分布；图的厚度；地图计数；交叉数

英文摘要： Topological graph theory is an important branch of graph theory. To determine the genus and the embedding distribution of a graph are NP-hard, as well the classic and key problems in topological graph theory, which have attracted the attention and study o

英文关键词： the genus of graphs；the embedding distribution；the thickness of graphs；the enumerating of maps；the crossing number