LOWER BOUNDS FOR PLANAR ORTHOGONAL DRAWINGS OF GRAPHS

被引：22

作者：

TAMASSIA, R ^{[1
]}

TOLLIS, IG ^{[1
]}

VITTER, JS ^{[1
]}

机构：

[1] UNIV TEXAS,DEPT COMP,RICHARDSON,TX 75083

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 39卷 / 01期

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL GEOMETRY; PLANAR EMBEDDING; VLSI LAYOUT; ORTHOGONAL DRAWING; BENDS;

D O I：

10.1016/0020-0190(91)90059-Q

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study planar orthogonal drawings of graphs and provide lower bounds on the number of bends along the edges. We exhibit graphs on n vertices that require-OMEGA(n) bends in any layout, and show that there exist optimal drawings that require-OMEGA(n) bends and have all of them on a single edge of length-OMEGA(n2). This work finds applications in VLSI layout, aesthetic graph drawing, and communication by light or microwave.

引用

页码：35 / 40

页数：6

共 10 条

[1]

DOLEV D, 1984, ADV COMPUTING RES, V2, P147

[2]

EADES P, 1989, CS8908 BROWN U DEP C

[3]

EADES P, 1991, IN PRESS NETWORKS

[4]

KHULLER S, 1990, UNPUB LATTICE STRUCT

[5] ON MINIMAL-NODE-COST PLANAR EMBEDDINGS [J].

STORER, JA .

NETWORKS, 1984, 14 (02) :181-212

[6] PLANAR GRID EMBEDDING IN LINEAR TIME [J].

TAMASSIA, R ;

TOLLIS, IG .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1989, 36 (09) :1230-1234

[7] ON EMBEDDING A GRAPH IN THE GRID WITH THE MINIMUM NUMBER OF BENDS [J].

TAMASSIA, R .

SIAM JOURNAL ON COMPUTING, 1987, 16 (03) :421-444

[8]

TAMASSIA R, 1990, UNPUB PARALLEL CONST

[9]

Tarjan R.E, 1983, CBMS NSF REGIONAL C, V44

[10] AMORTIZED COMPUTATIONAL-COMPLEXITY [J].

TARJAN, RE .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (02) :306-318

← 1 →