Research on Combinatorial Geometry

闭曲面的三角剖分和四边形剖分是与几何曲面相关的最典型的组合对象。我们首先考虑通过局部变形序列将一个三角剖分(或四边形剖分)转换到另一个三角剖分(或四边形剖分)的问题。继续前面的研究，我们得到了一些关于度约束情况和外三角剖分的结果，外三角剖分是外平面图的推广。我们还得到了一个关于平面三角剖分的有趣结果，它可以嵌入到另一个曲面的四边形剖分中。特别是，它依赖于曲面的方向性，而三角剖分的某些组合结构起着关键作用。四边形的着色具有仅出现在不可定向曲面上的类似现象。如果四边形有一个圈将曲面切割成可定向的曲面，则它的色数至少为4.特别地，环面和Klein瓶的四边形的色数由图的拓扑不变量和代数不变量决定.3连通图G在一个曲面上的高代表性使得我们可以把G割成一个合适的平面图.我们已经建立了一种非常有用的工具来描述这种切割。利用这个工具，我们证明了曲面上的3-连通图在某种意义上接近哈密顿的几个定理；关于最大度不超过4的生成树，最大度不超过8的2-连通子图，以及给定大小的轻连通子图。

Triangulations and Quadrangulations of a closed surface are most typical combinatorial objects related with geometic ones. We first consider the problem to transform one triangulation (or quadrangulation) to another by a sequence of local deformations. Continued to the preceding research, we have obtained some results for degree constrained cases and for outer-triangulations, a generalization of outer planar graphs. We have also obtained an interesting result on planar triangulations which can be embedded as a quadrangulation of another surface. In particular, it depends on the orientability of the surface, and certain combinatorial structure of the triangulation plays a key role.Coloring of quadrangulation has a similar phenomenon that appears in only nonorientable surfaces. If the quadrangulation has a cycle cutting the surface into orientable one, then the chromatic number is at least 4. In particular, the chromatic number of a quadrangulation of torus and Klein bottle is determined by a topological and algebraic invariant of the graph.High representativity of a 3-connected graph G on a surface enable us to cut open G into a suitable plane graph. We have established a very useful tool describing such a cutting. Using this tool, we have proved several theorems that show 3-connected graphs on a surface are close to be hamiltonian in a sense ; concerning spanning tree with maximum degree at most four, spanning 2-connected subgraph with maximum degree at most eight, and light connected subgraphs with given size.