A vertex-face assignment for plane graphs

被引：4

作者：

Souvaine, Diane L. ^{[2
]}

Toth, Csaba D. ^{[1
,3
]}

机构：

[1] Univ Calgary, Dept Math, Calgary, AB T2N 1N4, Canada

[2] Tufts Univ, Dept Comp Sci, Medford, MA 02155 USA

[3] MIT, Cambridge, MA 02139 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2009年 / 42卷 / 05期

关键词：

Plane straight line graph; Pseudo-triangulation; Encompassing graph; PSEUDO-TRIANGULATIONS;

D O I：

10.1016/j.comgeo.2008.06.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For every planar straight line graph (PSLG), there is a vertex-face assignment such that every vertex is assigned to at most two incident faces, and every face is assigned to all its reflex corners and one more incident vertex. Such an assignment allows us to augment every disconnected PSLG into a connected PSLG such that the degree of every vertex increases by at most two. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：388 / 394

页数：7

共 10 条

[1]

[Anonymous], P 21 ANN ACM S COMP

[2]

Bose P, 2001, DISCRETE COMPUT GEOM, V26, P387, DOI 10.1007/s00454-s001-0042-y

[3]

BROOKS RL, 1975, PHILIPS RES REP, V30, P205

[4] RAY SHOOTING IN POLYGONS USING GEODESIC TRIANGULATIONS [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GRIGNI, M ;

GUIBAS, L ;

HERSHBERGER, J ;

SHARIR, M ;

SNOEYINK, J .

ALGORITHMICA, 1994, 12 (01) :54-68

[5] Planar minimally rigid graphs and pseudo-triangulations [J].

Haas, R ;

Orden, D ;

Rote, G ;

Santos, F ;

Servatius, B ;

Servatius, H ;

Souvaine, D ;

Streinu, I ;

Whiteley, W .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2005, 31 (1-2) :31-61

[6]

Henneberg L., 1911, GRAPHISCHE STAT STAR

[7]

Hoffmann M, 2004, LECT NOTES COMPUT SC, V3111, P442

[8] Tight degree bounds for pseudo-triangulations of points [J].

Kettner, L ;

Kirkpatrick, D ;

Mantler, A ;

Snoeyink, J ;

Speckman, B ;

Takeuchi, F .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 25 (1-2) :3-12

[9] Combinatorial pseudo-triangulations [J].

Orden, David ;

Santos, Francisco ;

Servatius, Brigitte ;

Servatius, Herman .

DISCRETE MATHEMATICS, 2007, 307 (3-5) :554-566

[10]

Streinu I, 2005, DISCRETE COMPUT GEOM, V34, P587, DOI 10.1007/s00454-005-1184-0

← 1 →