CCE Theses and Dissertations
Formalization of a Slicing Hierarchy And Development of Associated Procedures For Rectangular Dualization From A Four-Completion using Wall Dominance
Date of Award
1994
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Center for Computer and Information Sciences
Advisor
Jacques Levin
Committee Member
Matthew He
Committee Member
S. Kundu
Committee Member
George K. Fornshell
Abstract
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.
NSUWorks Citation
John Sam Moore Jr.. 1994. Formalization of a Slicing Hierarchy And Development of Associated Procedures For Rectangular Dualization From A Four-Completion using Wall Dominance. Doctoral dissertation. Nova Southeastern University. Retrieved from NSUWorks, Center for Computer and Information Sciences. (733)
https://nsuworks.nova.edu/gscis_etd/733.