On the mathematical formulation of the wiring problem

The wiring problem is usually transformed into a graphtheoretical analysis‐synthesis problem. For a practical algorithm it is necessary that certain constraints are taken into account in the construction of the respective graph. These constraints originate from the desire to place terminals—eventually in a previously determined sequence—at the periphery of the board or the wiring layer of an integrated circuit (IC). For printed boards we can also have some demands regarding the sequence of contacts and the side on which the components have to be placed. The purpose of this paper is to show how these requirements, which are indispensible for a proper printed board layout, can be examined. Some of these requirements have not appeared in literature before. The inquiry consists of two separate tests, each eventually combined with modification steps. The details of these modifications are not a subject of this paper. In the last section the content of this paper is compared with other publications in this field.