双层板布线分层与借孔压缩的图论方法

本文提出的先布线、再通过图论方法分层的布线策略可以使线路布得比较均匀,大大压缩借孔数目。文中引入了“色边权”、“色次”等概念,证明了有关最大偶子图的一些引理和最佳着色的充要条件,给出了一个最佳着色算法,并提出解决借孔压缩问题的两个实用方法。