Planar topological routing
Andrew E. B. Lim, V. Thanvantri, Sartaj K. Sahni · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1997
We develop a simple linear time algorithm to determine if a collection of two-pin nets can be routed, topologically, in a plane (i.e., single layer). Experiments indicate that this algorithm is faster than the linear time algorithm of Marek-Sadowska and Tarng. Topological routability testing of a collection of multipin nets is shown to be equivalent to planarity testing, and a simple linear time algorithm is developed for the case when the collection of modules remains connected following the deletion of all nets with more than two pins.