权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Research on Combinatorial Geometry

组合几何研究

基本信息

批准号：
11640135
负责人：
OTA Katsuhiro
金额：
$ 2.24万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

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.

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