A 2D - 1 LOWER-BOUND FOR 2-LAYER KNOCK-KNEE CHANNEL ROUTING

This paper describes a two-point net channel routing problem with dens ity d that requires channel width 2d-1 in the two-layer knock-knee cha nnel routing model. This means that the (2d-1)-track algorithms of Riv est, Baratz, and Miller [1981 CMU Conference on VLSI Systems and Compu tations, Oct. 1981, pp. 153-159], Bolognesi and Brown [unpublished man uscript, Coordinated Science Laboratory, University of Illinois at Urb anna-Champaign, 1982], Frank [Combinatorica, 2 (1982), pp. 361-371], M ehlhorn Preparata, and Sarrafzadeh [University of Saarbrucken Tech. Re p., Saarbrucken, Germany, Nov. 1984], and Berger et al. [J. Assoc. Com put. Mach., 1994, to appear], are, in some cases, optimal. Thus, any i mprovement of these must rely on problem features other than density ( such as flux [Advances in Computing Research 2 (VLSI Theory), F. P. Pr eparata, ed., JAI Press, Greenwich, CT, 1984, pp. 205-229]) or must ma ke fundamental changes in the wiring model (such as increasing the num ber of layers [IEEE Trans. Comput., C-33 (1984), pp. 427-437] or allow ing wires to overlap [see Berger et al., above), [Algorithmica, 1 (198 6), pp. 223-232]).