ON THE OPTIMAL LAYOUT OF PLANAR GRAPHS WITH FIXED BOUNDARY

被引：13

作者：

BECKER, B

HOTZ, G

机构：

来源：

SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 05期

关键词：

INTEGRATED CIRCUITS - Computer Aided Design;

D O I：

10.1137/0216061

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the (optimal) layout of graphs with fixed boundary (i. e. , graphs, where only the nodes of a given cycle of the graph have fixed positions in the plane). The investigated layouts are straight line embeddings in a continuous part of the plane; the cost of a layout is calculated with help of very general cost functions including the pth power of the usual Euclidean distance metric for p equals 2,3,. . . (for short, l//p-metric). For a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, we show the existence and uniqueness of the optimal layout.

引用

页码：946 / 972

页数：27

共 23 条

[1]

BECKER B, 1985, P S THEORETICAL ASPE, P21

[2]

BECKER B, SFB124B1 U SAARL TEC

[3]

BECKER B, 1982, THESIS U SAARLANDES

[4]

BREUER MA, 1972, DESIGN AUTOMATION DI, V1

[5]

BRYANT R, 1983, 3RD CALTECH C VLSI B

[6]

Donath W.E., 1980, 17TH P DES AUT C, P412

[7]

FISCHER MJ, 1980, 12 P ACM STOC, P177

[8] ACCEL - AUTOMATED CIRCUIT CARD ETCHING LAYOUT [J].

FISK, CJ ;

CASKEY, DL ;

WEST, LE .

PROCEEDINGS OF THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, 1967, 55 (11) :1971-+

[9]

GROH U, 1984, BEITRAGE ALGEBRA GEO, V18, P191

[10]

GROH U, 1983, THESIS U SAARLANDES

← 1 2 3 →