Rectilinear Steiner Minimum Tree Formation using an Improved Augmented Line Segment Based Algorithm with Edge Reversal

An improvement to Augmented Line Segment Based Algorithm is proposed incorporating Edge reversal to generate a Rectilinear Steiner Minimum Tree with an objective of tree length reduction. Rectilinear Steiner Minimum Tree connects the given collection of points by means of horizontal and vertical line segments, with the aid of additional points called Steiner Points. Steiner points are introduced to reduce the total length of the tree and to connect in rectilinear manner since the distance between two points is measured in rectilinear metric. The algorithm constructs a Rectilinear Steiner Minimum Tree by augmenting the line segments drawn in four directions from all the points and adding an edge to the tree when two line segments overlap. The reversal of the two L-shaped layouts or edges is done when an overlap count of either of one increases thereby reducing the cost or length of the final tree formed. Rectilinear Steiner Minimum Tree is widely used in global routing phase of VLSI design and wire length estimation