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.
| Date of Award | Jan 1 1994 |
|---|
| Original language | English |
|---|
| Supervisor | Jacques Levin (Supervisor), Matthew He (Advisor), S. Kundu (Advisor) & George K. Fornshell (Advisor) |
|---|