两类三正则图最大亏格的新有效算法  

A New Effective Algorithm for the Maximum Genus of Two Types of 3-regular Graphs

作　　者：董广华[1,2] 刘彦佩[2] 王宁[3] 

机构地区：[1]天津工业大学理学院数学系,天津300160 [2]北京交通大学数学系,北京100044 [3]天津财经大学信息科学与技术系,天津300222

出　　处：《应用数学》2009年第2期430-436,共7页Mathematica Applicata

基　　金：国家自然科学基金部分资助(10571013)

摘　　要：本文借助联树模型给出了一些已知结果的新证明,并证明了图类Pn的上可嵌入性,提供了求强Pn图Pn*最大亏格的一个线性算法.In this paper, armed with the joint-tree model, the new proof of some known results are provided. Furthermore, the graph , which is called polder in this paper, are proved to be upper embeddable,and a linear time algorithm for determining the maximum genus of strong-polder are offered as well.

关 键 词：联树 最大亏格 图的嵌入 

分 类 号：O157.5[理学—数学]