G-Tree: Gravitation-Direction-Based Rectilinear Steiner Minimal Tree Construction Considering Bend Reduction

This paper presents a RSMT algorithm based on gravitation direction, namely G-Tree. It uses the gravitation a point receives from other points to judge its moving direction. Some weights are added to the calculation to reduce the number of bends, which is helpful for via reduction and reliability increment in the routing phase. After the construction, some refinements are taken to reduce bends further more. G-Tree has been implemented and tested. The experimental results show that G-Tree can reduce numbers of bends.