Does contraction preserve triangular meshes?

被引:2
作者
Ciarlet, P
Lamour, F
机构
[1] CEA,LV,F-94195 VILLENEUVE ST GEO,FRANCE
[2] BRANCHE CEA DEF,CISI,F-91192 GIF SUR YVETTE,FRANCE
关键词
D O I
10.1007/BF02207695
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A triangular graph is a planar graph in which each face is a 3-cycle, except possibly for the exterior face, and without articulation nodes. The embedding of a triangular graph in the plane is called a triangular mesh. More generally, a triangular graph with multiple contours is a planar graph without articulation nodes in which each face is a 3-cycle, except possibly for a fixed number of them. A contraction along an edge in a graph is the result of identifying the two endpoints of the edge. In this paper a necessary and sufficient condition is shown for which triangularity (possibly with multiple contours) is preserved after contraction. Moreover, when a licit contraction is performed, the question to answer is whether or not it is possible to derive the embedding of the contracted triangular graph from the original triangular mesh by redrawing only around the contraction zone.
引用
收藏
页码:201 / 223
页数:23
相关论文
共 12 条
[1]  
[Anonymous], 1987, WILEY INTERSCIENCE S
[2]   AN APPROACH TO THE GENERATION OF TRIANGULAR GRIDS POSSESSING FEW OBTUSE TRIANGLES [J].
DELJOUIERAKHSHANDEH, K .
INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 1990, 29 (06) :1299-1321
[3]  
FOULDS LR, 1994, GRAPH THEORY APPL
[4]  
GEORGE PL, 1991, 1414 INRIA
[5]  
Harary F., 1969, GRAPH THEORY
[6]  
KAMPEN GR, 1976, DISCRETE MATH, V4, P337
[7]   DOES A POINT LIE INSIDE A POLYGON [J].
MILGRAM, MS .
JOURNAL OF COMPUTATIONAL PHYSICS, 1989, 84 (01) :134-144
[8]  
Nishizeki T., 1988, ANN DISCRETE MATH, V32
[9]  
READ RC, 1987, C NUMER, V56, P31
[10]   CHECKING WHETHER A POINT LIES INSIDE A POLYGON [J].
WOOFF, C .
COMPUTER PHYSICS COMMUNICATIONS, 1985, 36 (02) :219-222