
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced PlaneSweep Method
Toru AWASHIMA Masao SATO Tatsuo OHTSUKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E76A
No.4
pp.507512 Publication Date: 1993/04/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computer aided design, LSI design technology, layout design, compaction, planesweep method,
Full Text: PDF>>
Summary:
This paper presents an optimal constraint graph generation algorithm for graphbased onedimensional layout compaction. The first published algorithm for this problem was the shadowpropagation algorithm. However, without sophisticated implementation of a shadowfront, complexity of the algorithm could fall into O(n^{2}), where n is the number of layout objects. Although our algorithm, called the enhanced planesweep based graph generation algorithm, is an extension of the shadowpropagation algorithm, such a drawback is resolved by introducing an enhanced planesweep technique. The algorithm maintains multiple shadowfronts simultaneously by storing them in a worklist called previousboundary. Since a balanced search tree is selected for implementation of the worklist, total complexity of the algorithm is O(n log n) which is optimal. Experimental results show that the enhanced planesweep based graph generation algorithm runs in almost linear time with respect to the number of layout objects and is faster than the perpendicular planesweep algorithm which is also optimal in terms of time complexity.

