A Via Minimization Algorithm for Two-Layer Channel Routing

Two graphs, calkd layering graph and ordering graph respectively, are defined in this paper. Based on them, the via minimization problem for two-layer channel routing can be formulated as transforming layering giaph into a 2-colourable graph by partitioning minimum number of nets. A lemma which describes the minimum number of vias. required for two-layer channel routing is given here, and a via minimization algonthm for two-layer channel routing is presented too.