论文部分内容阅读
针对4-正则图的平面嵌入的纵横扩张的特殊性，某些4-正则图类的最小折数纵横扩张已经有了线性算法。本文通过基纵横扩张，提供了从一个4-正则图扩充为另一个4-正则图的方式，使得从原图的最小折数基纵横扩张自然导出扩充图的最小折数基纵横扩张。全文共分六章：
第一章介绍了一些基本概念及相关的定理。
第二章在刘彦佩教授对图的可嵌入性研究的基础上建立了广平衡图的运输问题模型。
第三章在广平衡图模型的基础上，得到了最小折数纵横扩张的判别准则。
第四章讨论了4-正则平面图的特殊性质，并得到了它的最优纵横扩张的判别准则。
第五章给出了求一类4-正则平面图最优纵横扩张的算法，并利用第四章得到的判别准则从理论上进行了论证。
第六章总结了全文的结论。