For very-large-scale integrated circuit (VLSI) layout planning using rectangular dissections to represent a hierarchy of conceptualization and modular refinement, the writer has defined a mathematical formalization called a hierarchy. Using Szepieniec's and Otten's (1980) restricting of the usual dissecting partitioning only to vertical and horizontal slicing as progressive restrictions of Flemming's (1977, 1978) T-plan and Kundu's and Singh's (1 987; Kundu, technical report #86-021) T*-plan, the writer adds his null-partitioning for flexibility in using the s-hierarchy. The illustrated use of lexicographic ordering of the hierarchal levels offers additional flexibility. For the case where intermediate hierarchal-level information is given by the weak dual graph of the level's partial dissection, the writer develops the n-fillable path as an aid in identifying wall and wall-dominance structure, using the assumption that the weak dual has a 4-completion (Kozminski & Kinnen, 1984). Upon this path concept he builds the more elaborate structures of the single-wall laminate, the multiple-wall shell, and the subrectangle-defining 3-booth. A principal result of the paper is the 3-booth's defining a subregion node in the dissection tree.
Being considered as an isolated rectangle, this sub region can be subjected to dualization techniques developed by Kinnen and Kozminsky (1984, 1985, 1988; cr. Kozminski, 1985). The writer gives a rather extensive introduction to the theory of rectangular dissections and their dual (adjacency) graphs, as well as numerous citations in the literature pertaining to the development of rectangular dissection theory.
| Identifer | oai:union.ndltd.org:nova.edu/oai:nsuworks.nova.edu:gscis_etd-1732 |
| Date | 01 January 1994 |
| Creators | Moore, John Sam, Jr. |
| Publisher | NSUWorks |
| Source Sets | Nova Southeastern University |
| Detected Language | English |
| Type | text |
| Source | CEC Theses and Dissertations |
Page generated in 0.0019 seconds