In this thesis, we consider the problem of finding the minimum rectilinear Steiner tree which has the minimum number of vias. Given a set of n points on the boundary of a rectangle, we find a tree which connects the points using only horizontal and vertical lines with objectives. First objective is to minimize the number of vias at which horizontal and vertical lines of the tree are connected. Second objective is to minimize total length of the tree. This problem can be applied to the well-known two-layer wire routing subject to the horizontal-vertical rule.
We present an O(n) time algorithm for this problem using the dynamic programming approach.
