基于结构图论的一般图嵌入分布的研究

The embedding distribution of graphs and the enumeration of rooted maps are two equivalent problems of the enumeration theory on graphs embedding into surfaces. It is a topological invariant of a graph into a surface and an active research area in modern topological graph theory. Known from the published literatures, most results were related to the enumeration of embeddings of graphs into surfaces with lower genus and the embedding distribution of some special classes of graphs. We have already derived recurrence formula for 3-regular outerplanar graphs and known that outerplanar graphs are of tree-width 2. Moreover, we have a formula for genus distributions of fan graphs, which are outerplanar graphs with a single vertex of high valence. Our research plan is seek to develop some new methods to investigate the embedding distributions all bounded tree-width graphs by applying tree decomposition and topological methods, which methods will mainly base on such some theories as the structure theory presented by Robertson and Seymour, overlap matrix , joint tree theory , characters of symmetric groups and so on. We also develop method to study genus distribution of a digraph. A positive solution would be a polynomial-time algorithm for exact values or reasonably tight approximations. A negative solution would be proof that the problem is NP-hard. Besides, employing the enumerating theory on rooted maps and the algebraic representation of the map presented by Tutte, we systematically investigate the nonorientable embedding distribution on the graph of high valence by extending orientable permutation partitions.

图的嵌入分布是全面刻画图在曲面上嵌入的一个拓扑不变量、是当代拓扑图论最活跃的研究课题之一。以往结果多侧重于研究低亏格曲面的上图的嵌入计算及一些特殊图类的嵌入分布，较少涉及一般图类的嵌入分布。本项目在我们前期工作已获得一般3-正则外平面图(树宽为2)及一般3-正则Halin图（树宽为3）的嵌入分布的基础上， 基于Robertson 与Seymour所发展起来的结构图理论，运用树分解、矩阵理论，曲面组合学理论，对称函数理论、有限群表示理论等组合、分析、代数及拓扑方法，发展新的运算等研究下述问题：（I）树宽为2的图的嵌入分布；（II）树宽为3的图的嵌入分布；(III) 给定树宽图的嵌入分布；(IV) 有向图的嵌入分布。积极的结果将得到这些图类的嵌入分布的精确值与渐近值，研究结果除将进一步丰富曲面组合学外、也将进一步加深分析、代数等工具在拓扑图论中的交叉应用。

图的嵌入分布是全面刻画图在曲面上嵌入的一个拓扑不变量、是当代拓扑图论活跃的研究课题之一。以往结果多侧重于研究低亏格曲面的上图的嵌入计算及一些特殊图类的嵌入分布，较少涉及一般图类的嵌入分布。本项目在我们前期工作的基础上， 基于Robertson 与Seymour所发展起来的结构图理论，运用树分解、矩阵理论，曲面组合学理论，对称函数理论、有限群表示理论等组合、分析、代数及拓扑方法，发展新的运算等研究下述问题：（I）树宽为2的图的嵌入分布；（II）树宽为3的图的嵌入分布；(III) 给定树宽图的嵌入分布；(IV) 有向图的嵌入分布。 . 申请人在项目执行期间主要获得了如下重要结果：.1.在不可定向嵌入分布的计算，我们提出了一套新的组合拓扑工具与方法，引入了计算不可定向亏格分布的一般途径，并得到了最大度给定的固定树图的不可定向嵌入分布多项式算法。 .2. 我们对证明了Spider-like图类的(欧拉）亏格多项式满足k-阶齐次线性差分方程(k>=1)。 .3. 我们解决了轮图的亏格分布这一近30年的公开问题。