DISTANCE VISIBILITY GRAPHS

被引：11

作者：

Coullard, Collette ^{[1
]}

Lubiw, Anna ^{[2
]}

机构：

[1] Northwestern Univ, Dept Ind Engn & Management Sci, Evanston, IL 60208 USA

[2] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1992年 / 2卷 / 04期

关键词：

Visibility graph; Euclidean distance representation; k-connected; spanning k-tree;

D O I：

10.1142/S0218195992000202

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A new necessary condition for a graph G to be the visibility graph of a simple polygon is given: each 3-connected component of G must have a vertex ordering in which every vertex is adjacent to a previous 3-clique. This property is used to give an algorithm for the distance visibility graph problem: given an edge-weighted graph G, is it the visibility graph of a simple polygon with the given weights as Euclidean distances?

引用

页码：349 / 362

页数：14

共 23 条

[1] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :305-314

[2] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[3]

Bern M. W., 1987, THESIS U CALIFORNIA

[4]

Cai L., 1991, DISCRETE APPL UNPUB

[5] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524

[6] A COMBINATORIAL DECOMPOSITION-THEORY [J].

CUNNINGHAM, WH ;

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1980, 32 (03) :734-765

[7] FIXED EDGE-LENGTH GRAPH DRAWING IS NP-HARD [J].

EADES, P ;

WORMALD, NC .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (02) :111-134

[8]

ELGINDY HA, 1985, THESIS MCGILL U MONT

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

EVERETT, H ;

CORNEIL, DG .

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

[10]

Everett H, 1990, THESIS U TORONTO TOR

← 1 2 3 →