Rectangular dualization and rectangular dissections

Author

Kozminski, Krzysztof A. ; Kinnen, E.

Author_Institution

Rochester Univ., NY, USA

Volume

35

Issue

11

fYear

1988

fDate

11/1/1988 12:00:00 AM

Firstpage

1401

Lastpage

1416

Abstract

Rectangular dualization refers to finding a dual of a planar graph, that can be drawn in the form of a rectangular dissection; it has applications in architectural design and in the floorplanning of VLSI ICs. The authors present properties of rectangular dissections and discuss two related topics: (1) a problem of enumerating without repetitions all rectangular duals of a graph; and (2) transformations of rectangular dissections. The authors have developed a fast algorithm for enumerating rectangular duals that is based on a limited set of possible local changes in the structure of a rectangular dissection. A second procedure for systematically generating all rectangular duals of a graph is developed from the notion of partitioning the sets of rectangular dissections into disjoint subsets

Keywords

VLSI; circuit layout; graph theory; network topology; VLSI ICs; architectural design; circuit layout; disjoint subsets; fast algorithm; floorplanning; planar graph; rectangular dissections; rectangular duals; transformations; Application specific integrated circuits; Constraint theory; Graph theory; Helium; Microelectronics; Optimization methods; Partitioning algorithms; Terminology; Very large scale integration; Wiring;

fLanguage

English

Journal_Title

Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0098-4094

Type

jour

DOI

10.1109/31.14464

Filename

14464