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


Document Type


Degree Name

Doctor of Philosophy (PhD)


Center for Computer and Information Sciences


Jacques Levin

Committee Member

Matthew He

Committee Member

S. Kundu

Committee Member

George K. Fornshell


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.

This document is currently not available here.

  Link to NovaCat