Geodesic
Generating All Triangulations of Plane Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009) , Tome 15 (2011) no. 3, pp. 457-482.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this paper, we deal with the problem of generating all triangulations of plane graphs. We give an algorithm for generating all triangulations of a triconnected plane graph G of n vertices. Our algorithm establishes a tree structure among the triangulations of G, called the "tree of triangulations," and generates each triangulation of G in O(1) time. The algorithm uses O(n) space and generates all triangulations of G without duplications. To the best of our knowledge, our algorithm is the first algorithm for generating all triangulations of a triconnected plane graph; although there exist algorithms for generating triangulated graphs with certain properties. Our algorithm for generating all triangulations of a triconnected plane graph needs to find all triangulations of each face (a cycle) of the graph. We give an algorithm to generate all triangulations of a cycle C of n vertices in time O(1) per triangulation, where the vertices of C are numbered. Finally, we give an algorithm for generating all triangulations of a cycle C of n vertices in time O(n2) per triangulation, where vertices of C are not numbered. Key words: Triangulation; Graph; Cycle; Plane Graph; Genealogical Tree.
DOI : 10.7155/jgaa.00234
Keywords: Triangulation, Graph, Cycle, Plane Graph, Genealogical Tree 
@article{JGAA_2011_15_3_a6,
     author = {Mohammad Tanvir Parvez and Md. Saidur Rahman and Shin-ichi Nakano},
     title = {Generating {All} {Triangulations} of {Plane} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {457--482},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2011},
     doi = {10.7155/jgaa.00234},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00234/}
}
TY  - JOUR
AU  - Mohammad Tanvir Parvez
AU  - Md. Saidur Rahman
AU  - Shin-ichi Nakano
TI  - Generating All Triangulations of Plane Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 457
EP  - 482
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00234/
DO  - 10.7155/jgaa.00234
LA  - en
ID  - JGAA_2011_15_3_a6
ER  - 
%0 Journal Article
%A Mohammad Tanvir Parvez
%A Md. Saidur Rahman
%A Shin-ichi Nakano
%T Generating All Triangulations of Plane Graphs
%J Journal of Graph Algorithms and Applications
%D 2011
%P 457-482
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00234/
%R 10.7155/jgaa.00234
%G en
%F JGAA_2011_15_3_a6
Mohammad Tanvir Parvez; Md. Saidur Rahman; Shin-ichi Nakano. Generating All Triangulations of Plane Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
					, Tome 15 (2011) no. 3, pp. 457-482. doi : 10.7155/jgaa.00234. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00234/

Cité par Sources :