Given a set of obstacles and two distinguished points in the plane the
problem of finding a collision-free path subject to a certain optimiz
ation function is a fundamental problem that arises in many fields, su
ch as motion planning in robotics, wire routing in VLSI and logistics
in operations research. In this survey we emphasize its applications t
o VLSI design and limit ourselves to the rectilinear domain in which t
he goal path to be computed and the underlying obstacles are all recti
linearly oriented, i.e., the segments are either horizontal or vertica
l. We consider different routing environments, and various optimizatio
n criteria pertaining to VLSI design, and provide a survey of results
that have been developed in the past, present current results and give
open problems for future research.