4-正则图的纵横扩张优化  

Optimization of rectilinear extensions of 4-regular graphs

作　　者：兰培挺[1] 刘彦佩[1] 

机构地区：[1]北京交通大学数学系,北京100044

出　　处：《周口师范学院学报》2006年第5期5-8,共4页Journal of Zhoukou Normal University

基　　金：国家自然科学基金资助项目(No.60373030)

摘　　要：针对4-正则图的平面嵌入的纵横扩张的特殊性,某些4-正则图类的最小折数纵横扩张已经有了线性算法.本文通过基纵横扩张,提供了从一个4-正则图扩充为另一个4-正则图的方式,使得从原图的最小折数基纵横扩张自然导出扩充图的最小折数基纵横扩张.According to the properties of rectilinear extensions of 4-regular graphs, a linear time algorithm is designed to get rectilinear extensions of some particular kinds of 4-regular graphs with the minimum total number of bends. In this paper , a generalized algorithm is provided to extend a 4-regular graph to another 4-regular graph through base rectilinear extension, through which the base rectilinear extension with the minimum total number of bends of the extended ,t-regular graph is naturally obtained from that of the original one.

关 键 词：4-正则图 纵横扩张 广平衡图 基纵横扩张 规范图 

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