RECOGNIZING VISIBILITY GRAPHS OF SPIRAL POLYGONS

被引：28

作者：

EVERETT, H ^{[1
]}

CORNEIL, DG ^{[1
]}

机构：

[1] UNIV TORONTO, DEPT COMP SCI, TORONTO M5S 1A4, ONTARIO, CANADA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1990年 / 11卷 / 01期

基金：

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

关键词：

D O I：

10.1016/0196-6774(90)90026-B

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The recognition problem for visibility graphs is, given a graph, to determine whether it is the visibility graph of a simple polygon. The complexity of this problem is unknown. In this paper we show how to determine, in linear time, whether a graph is the visibility graph of a spiral polygon. © 1990.

引用

页码：1 / 26

页数：26

共 9 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[3]

ELGINDY HA, 1985, THESIS MCGILL U MONT

[4] INCIDENCE MATRICES AND INTERVAL GRAPHS [J].

FULKERSON, DR ;

GROSS, OA .

PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+

[5]

GHOSH SK, 1986, JHUEECS8614 J HOPK U

[6] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].

GILMORE, PC ;

HOFFMAN, AJ .

CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&

[7]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[8] FINDING HAMILTONIAN CIRCUITS IN INTERVAL-GRAPHS [J].

KEIL, JM .

INFORMATION PROCESSING LETTERS, 1985, 20 (04) :201-206

[9]

Lekkerkerker C. G., 1962, FUND MATH, V51, P45, DOI DOI 10.4064/FM-51-1-45-64

← 1 →