Finding a Maximum-Density Planar Subset of a Set of Nets in a Channel

We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case running time is still O(n^3), this algorithm achieves better results when either t or w is of modest magnitude. In the very special case when there are no two-sided nets, the bound stated above becomes O(nlgn+nw); this bound can also be achieved in the case of no single-sided nets. In addition, the bounds stated so far can be strengthened by incorporating into the running time the number of edges in certain interval overlap and interval containment graphs.