A C-type class of mixed river routings

Previous work on the river routing problem yielded three successively larger classes of routings: internal, internal-external, and mixed. In this paper we con- sider a larger class of mixed routings which uses C-type mixed wires with jogs, as well as C-type cut throughs, to generate further reductions in vertical density and overall area. By starting with an optimal mixed routing, and selectively inserting C-type mixed wires with jogs, a new routing is generated which is potentially more compact than the optimal mixed, yet it retains the same channel width and markings of the nets. An O(n²) algorithm is presented for creating routings in this new C-type mixed class which utilize as many C-type mixed wires as possible without changing the net markings.