论文部分内容阅读
纵横嵌入的理论在超大规模集成电路设计中的应用前景已经显露无遗。作为其基础的一步就是研究一个平面嵌入的纵横扩张。确定最小折数扩张已经从理论上得到了有效算法。3-平面图的最小折数纵横嵌入问题可在多项式时间内解决。但4-平面图的最小折数纵横嵌入问题是NP-困难的。
本文在这一理论的基础上，进一步研究了三类特殊的4-正则图的最小折数纵横扩张问题，得到了确定这三类图的最小折数纵横扩张的简便算法。全文共分五部分：
第一部分为相关背景介绍；
第二部分介绍了一些基本定义及相关的概念；
第三部分是有关最小折数纵横扩张的判定定理；
第四部分在最小折数纵横扩张判定定理的基础上，求出了三类4-正则图纵横扩张的最小折数，分别给出了一个简便算法。
第五部分做出结论，并对一些问题做出展望。