Topology based routing algorithms for multilayer IC layout design

In this thesis, we consider the multilayer topological routing problem and also the geometric routing problem based on topological routing solution. We show that the problem of multilayer topological planar routing for any arbitrary routing region can be modeled as a problem in a simple closed routing region. We also show that the solution to the multilayer planar routing leads to a better result of the topological via minimization problem. We present a provably-good approximation algorithm for the multilayer topological planar routing problem for different routing regions.;We also propose a graph theoretic algorithm to find 2-layer topological solutions that are guaranteed to be transformable to geometric routing solution. The basic idea is to develop topological routing such that the congestions over the entire routing surface are uniform. An iterative algorithm is then applied to this topological solution to obtain a geometric routing. (Abstract shortened by UMI.).