A fast algorithm to test planar topological routability
Andrew E. B. Lim, Sartaj K. Sahni, V. Thanvantri · 2002
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 (1983).