@InProceedings{BR81,
  author =       { Donna Brown and Ronald L. Rivest },
  title =        { New Lower Bounds on Channel Width },
  pages = 	 { 178--185 },
  eventtitle =   { Proceedings CMU Conference on VLSI Systems and Computations },
  venue =        { Pittsburgh, Pennsylvania },                  
  eventdate =    { 1981-10 },                  
  publisher =    { Computer Science Press },
  editor =       { H. T. Kung and Bob Sproull and Guy Steele },
  date =         { 1981 },                  
  OPTyear =      { 1981 },
  OPTmonth = 	 { October },
  abstract =     {
        We present here a simple yet effective technique for calculating a lower
        bound on the number of tracks required to solve a given channel-routing
        problem.  The bound applies to the wiring model where horizontal wires run
        on one layer and vertical wires run on another layer.  One of the major
        results is that at least $\sqrt{2n}$ tracks are necessary for \underline{any}
        dense channel routing problem with $n$ two-terminal nets that begin and end
        in different columns.  For example if each net $i$ begins in column $i$ and
        ends in column $i+1$, at least $\sqrt{2n}$ tracks are required, even though
        the channel ``density'' is only 2.  This is the first technique which can give
        results that are significantly better than the naive channel density arguments.
        A modification results in the calculation of an improved bound, which we
        conjecture to be optimal to within a constant factor.
                 },
}