Invisible edge and soft tied in compaction strategy

In most conventional one-dimensional compaction technique, the objects are frequently tied together to reduce the computation complexity. The compactness of the resulting layout may, however, be reduced when the ties appear in the critical path. In this paper, this problem is solved by the soft tie which can be broken to relocate the objects position. The compactness is also limited by the extra edge used to avoid diagonal constraint violation. In addition, the wire terminating without any rigid object at its end can cause an additional vertex in the constraint graph. The number of these wires gradually increases after jog insertion is performed in each compaction step, thus the complexity will be increased. The invisible edge is proposed to solve this problem. Furthermore, any necessary jogs can be inserted automatically. The invisible edge and soft tie technique allows the one-dimensional compaction to gain the compactivity close to that obtained by the dimensional compaction within reasonable complexity O(N ²)