Floorplans, planar graphs and layouts
Floorplans, planar graphs and layouts
复制标题
平面图、平面图和布局
DOI：
10.1109/31.1739
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
I. Cederbaum
中科院分区：
文献类型：
--
作者：
S. Wimer;I. Koren;I. Cederbaum
讨论的主题是最小化的布局和相关的网络流和平面图的直线表示的结果，平面图和布局的图形模型的基础上所占用的面积。允许任意的平面布置图。在给定任意布图和嵌入积木块面积的情况下，证明了零浪费面积布局的存在唯一性，并给出了其充分必要条件.在此基础上，提出了一种生成零浪费面积版图的方法。给出对偶弧长积不变的对偶网络对族，证明了其最长路的最小积不小于其最短路的最大积.它还表明，在这样一个家庭的对偶网络对的流量的最大产品是由每个单独的对偶弧对的弧长积的总和。本文提出了一种求任意平面图的直线表示的有效方法。>
The topics discussed are minimization of the area occupied by a layout and related results concerning networks flow and rectilinear representation of planar graphs, based on a graph model of floorplans and layouts. Arbitrary floorplans are allowed. Given an arbitrary floorplan and the areas of the embedded building blocks, the existence and uniqueness of a zero wasted area layout are proved, and characterized by a necessary and sufficient condition. Based on this condition, a scheme is described to generate zero-wasted-area layouts. Given a family of dual network pairs for which the product of dual arc lengths are invariant, it is proved that the minimal product of their longest paths is not smaller than the maximal product of their shortest paths. It is also shown that the maximal product of the flows in such a family of dual network pairs is given by the total sum of the arc length product of each individual pair of dual arcs. An efficient procedure to derive a rectilinear representation for any planar graph is presented. >