Visibility graphs of towers

被引：9

作者：

Colley, P

Lubiw, A

Spinrad, J

机构：

[1] QUEENS UNIV,KINGSTON,ON,CANADA

[2] UNIV WATERLOO,DEPT COMP SCI,WATERLOO,ON N2L 3G1,CANADA

[3] VANDERBILT UNIV,NASHVILLE,TN

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1997年 / 7卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0925-7721(95)00033-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A tower is a polygon consisting of two reflex chains sharing one common endpoint, together with one edge joining the other endpoints of the chains. A linear time algorithm is given to recognize the [vertex] visibility graphs of towers, and these graphs are characterized as bipartite permutation graphs with an added Hamiltonian cycle. Similar results have been obtained independently by Choi, Shin and Chwa (1992).

引用

页码：161 / 172

页数：12

共 19 条

[1]

ABELLO J, 1992, UNPUB VISIBILITY GRA

[2]

[Anonymous], 1987, ART GALLERY THEOREMS

[3]

Brandstadt A., 1987, C NUMER, V58, P165

[4]

CHOI SH, 1992, 3 INT S ALG COMP ISA

[5]

COLLEY P, 1991, THESIS U WATERLOO WA

[6]

Colley P., 1992, P 4 CAN C COMP GEOM, P29

[7] DISTANCE VISIBILITY GRAPHS [J].

Coullard, Collette ;

Lubiw, Anna .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (04) :349-362

[8]

COURANT R, 1951, ELEMENTARY APPROACH

[9]

ELGINDY HA, 1985, THESIS MCGILL U MONT

[10] RECOGNIZING VISIBILITY GRAPHS OF SPIRAL POLYGONS [J].

EVERETT, H ;

CORNEIL, DG .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1990, 11 (01) :1-26

← 1 2 →