图的浸入理论及优化布局

On the basis of rectilinear immersion theory of a graph, in particular,.algorithms for optimally determining the schemes of routing and placements are constructed under certain conditions. Further, soltwares are considered for realizing them on a computer to provide some theoretical preparation for the automation of designs on layout of electrtronic circuits.

本项目拟进一步研究图的浸入理论，特别是非平面图的浸入理论，进而形成电子线路自动定位与布线的数学理论。着意解决各种存在性、最优性及渐进估计等问题；设计相应的算法，分析其复杂度并在计算机上实现。不仅可完善和丰富图的浸入理论，而且有应用到超大规模集成电路设计中去的前景，也将对技术科学的发展产生重要影响。