An optimal chip compaction method based on shortest path algorithm with automatic jog insertion
Awashima, Yamamoto Yamamoto, Sato, Ohtsuki · IEEE/ACM International Conference on Computer-Aided Design · 1992
A one-dimensional compaction method for layout patterns including rectilinear macrocells on any number of layers is presented. The algorithm is based on the shortest path search on a constraint graph. It generates an optimal layout pattern in the smallest area by introducing effective jogs in O (N log N) time, where N is the number of line segments of the input pattern and inserted jogs. The jogs are inserted by means of an enhanced plane-sweep method developed in the field of computational geometry. Performance data of an experimental program show its efficiency.>