Pad Minimization for Planar Routing of Multiple Power Nets

This paper discusses the problem of minimizing the number of power pads, in order to guarantee the existence of a planar routing of multiple power nets. We derive a general lower bound and discuss an heuristic for the general problem. We examine several important special cases, including the case of three power nets, and present optimal strategies for pad placement. We also show that the general pad minimization problem is NP-complete. © 1990 IEEE