两类4-正则图的最小折数纵横扩张  

Minimum Bend Rectilinear Extensions of Two Kinds of 4-Regular Graphs

作　　者：俞勤 刘彦佩[1] 杨燕[1] 

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

出　　处：《北京交通大学学报》2006年第6期77-80,84,共5页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

摘　　要：纵横嵌入的理论已被用在超大规模集成电路的设计中.确定最小折数扩张已经从理论上得到了有效算法.本文作者在这一理论的基础上,进一步研究了两个特殊的4_正则图类,得到了确定这两类图的最小折数纵横扩张的简便算法,并给出了这两类图的纵横扩张的最小折数.The theory of rectilinear embeddings of graphs has been used in the design of VLSI. The determination of minimum bends in a rectilinear extension of a graph has been solved with effective algorithm. Based on this theory, we discuss rectilinear extensions of two particular kinds of 4-regular graphs with the minimum total number of bends in this article, and obtain a simple algorithm as well as the minimum total number of bends.

关 键 词：图论 纵横扩张 最小折数 4-正则图 

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