On Ensuring Multilayer Wirability by Stretching Layouts

Every knock-knee layout is four-layer wirable. However, there are knock-knee layoutsthat cannot be wired in less than four layers. While it is easy to determine whether aknock-knee layout is one-layer wirable or two-layer wirable, the problem of determiningthree-layer wirability of knock-knee layouts is NP-complete. A knock-knee layout maybe stretched vertically (horizontally) by introducing empty rows (columns) so that it canbe wired in fewer than four layers. In this paper we discuss two different types ofstretching schemes. It is known that under these two stretching schemes, any knock-kneelayout is three-layer wirable by stretching it up to (4/3) of the knock-knee layoutarea (upper bound). We show that there are knock-knee layouts that when stretchedand wired in three layers under scheme I (II) require at least 1.2 (1.07563) of the originallayout area. Our lower bound for the area increase factor can be used to guide thesearch for effective stretching-based dynamic programming three-layer wiring algorithmssimilar to the one presented in [8]