@InProceedings{RBM81,
  author =       { Ronald L. Rivest and Alan E. Baratz and Gary [L.] Miller },
  title =        { Provably Good Channel Routing Algorithms },
  pages = 	 { 153--159 },
  booktitle =    { Proceedings CMU Conference on VLSI Systems and Computations },
  publisher =    { Computer Science Press },
  editor =       { H. T. Kung and Bob Sproull and Guy Steele },
  date =         { 1981 },                  
  OPTyear =      { 1981 },
  OPTmonth = 	 { October },
  eventtitle =   { CMU Conference on VLSI Systems and Computations },                
  venue =        { Pittsburgh, Pennsylvania },                  
  eventdate =    { 1981-10 },                  
  abstract =     {
        In this paper we present three new two-layer channel routing algorithms
        that are provably good in that they never require more thatn $2d-1$
        horizontal tracks where $d$ is the channel density, when each net 
        connects just two terminals.  To achieve this result we use a slightly
        relaxed (but still realistic) wiring model in which wires may run on
        top of each other for short distances as long as they are are on 
        different layers.  Two of our algorithms will never use such a
        ``parallel run'' of length greater than $2d-1$ and our third algorithm
        will require overlap only at jog points or cross points.  Since in this
        wiring model at least $d/2$ horizontal tracks are required, these
        algorithms produce a routing requiring no more than four times the
        best possible number of horizontal tracks.  The second algorithm
        also has the property that it uses uses at most $4n$ contacts, where
        $n$ is the number of nets being connected.                   
                 },
}