SOME RESULTS ON VISIBILITY GRAPHS

被引：15

作者：

ANDREAE, T

机构：

[1] Mathematisches Seminar, Universität Hamburg, D-2000 Hamburg 13

来源：

DISCRETE APPLIED MATHEMATICS | 1992年 / 40卷 / 01期

关键词：

D O I：

10.1016/0166-218X(92)90018-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph is a visibility graph if its vertices nu(l),...,nu(n) can be associated with disjoint horizontal line segments s(l),...,s(n) in the plane such that nu(i) and nu(j) are joined by an edge iff there exists a vertical line segment connecting s(i) with s(j) without intersecting any other s(k). Several authors have studied visibility representations of graphs in the context of integrated circuit layout. In particular, visibility graphs were investigated in the context of VLSI layout compaction. Among other results on visibility graphs we provide answers to questions posed in a paper of Tamassia and Tollis; for example we show that deciding whether a given graph is a visibility graph is an NP-complete problem.

引用

页码：5 / 17

页数：13

共 22 条

[1]

BONDY JA, 1976, GRAPH THEORY APPLICA

[2] ALGORITHMS FOR PLANE REPRESENTATIONS OF ACYCLIC DIGRAPHS [J].

DIBATTISTA, G ;

TAMASSIA, R .

THEORETICAL COMPUTER SCIENCE, 1988, 61 (2-3) :175-198

[3] MINIMUM PARTITION OF A MATROID INTO INDEPENDENT SUBSETS [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :67-+

[4]

Garey M. R., 1976, SIAM Journal on Computing, V5, P704, DOI 10.1137/0205049

[5] APPLICATION OF GRAPH COLORING TO PRINTED-CIRCUIT TESTING [J].

GAREY, MR ;

JOHNSON, DS ;

SO, HC .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS, 1976, 23 (10) :591-599

[6]

LIAO YZ, 1983, IEEE T COMPUT AID D, V2, P62

[7]

Lodi E., 1985, VLSI: Algorithms and Architectures. Proceedings of the International Workshop on Parallel Computing and VLSI, P125

[8]

LODI E, 1986, IEEE T COMPUT, V35, P923, DOI 10.1109/TC.1986.1676685

[9]

Lovasz L, 1986, ANN DISCRETE MATH

[10] A NOTE ON VISIBILITY GRAPHS [J].

LUCCIO, F ;

MAZZONE, S ;

WONG, CK .

DISCRETE MATHEMATICS, 1987, 64 (2-3) :209-219

← 1 2 3 →