The minimum track number of the narrower channel in the signal‐row single‐layer routing
Yoshifumi Manabe, Kenichi Hagihara, Nobuki Tokura · Electronics and Communications in Japan (Part I Communications) · 1985
Abstract Single‐row single‐layer routing is critically important for the design of printed circuit board or LSI. It is used to obtain realizations for minimal upper and lower channel track numbers U(R) and L(R) out of realizations R that are to make a connective relation without cross connection. Such a relation N̈ (net set) for a set of vertices on a straight line is given, such that (1) U(R) + + L(R), (2) max(U(R), L(R)) or (3) min(U(R), L(R)) can be decreased to a minimum, respectively. Among these tasks, the time complexity of (1) remains unresolved, and (2) has been proven to be NP‐complete. This paper discusses the problem (3), that is, to obtain a realization Rm that makes track number t either for upper or lower channel that has lower number of tracks as a minimum. We will introduce α(N̈), a tangle number of N̈, as a new measure and prove that the measure will be the minimal value of t. Also, we will present an algorithm to obtain α(N̈) and Rm and show that the time required for their computation be linear to the product of numbers of nets and vertices, even in the worst case. This is a fundamental problem that is to be applied to determination of the number of layers needed for a multilayer approach to realize a given net set on the condition that both the upper and lower channel track numbers be limited.