Channel routing is a basic problem in the design of
VLSI-circuits and has received considerable attention
in the past. There are essentially two different
routing models: {it Knock-knee routing} and {it
Manhattan routing}. We consider the knock-knee model;
only two terminal nets are involved. The {it channel
routing problem (CRP)} is given by a bounded rectangle
in a rectilinear grid (the {it channel}) and a
collection of pairs of terminals (called {it nets}),
where the {it input terminal} lies on the upper
boundary and the {it exit terminal} lies on the lower
boundary of the channel. The {it layout} consists of
edge-disjoint paths (called {it wires}) through the
channel connecting the input- and the exit terminal of
the nets. To avoid physical contacts between the wires,
the edges of the paths are assigned to different
layers, such that no two wires share a grid point in
the same layer (called {it wiring}). Connections
between distinct layers (called {it vias}) are placed
on grid points. For the design of algorithms solving
the layout respectively wiring problem the following
criteria are of central importance: The {it area of
the layout}, the {it length of the wires}, the {it
number of layers}, the it number of vias and the {it
complexity of the algorithm}. In this paper we present
two new algorithms, that guarantee good respectively
optimal solutions for these problems.
