1-1hit |
Noriya KOBAYASHI Masahiro ABE Toshinobu KASHIWABARA Sumio MASUDA
Suppose that there are terminals on two concentric circles Cin and Cout, with Cin inside of Cout. A set of two-terminal nets is given and the routing area is the annular region between the two circles. In this paper, we present an O(n2) time algorithm for testing whether the given net set is two-layer routable, where n is the number of nets. Applying this algorithm repeatedly, we can find, in O(n3) time, a maximal subset of nets which is two-layer routable.