Geodesic
Listing All Plane Graphs
Journal of graph algorithms and applications, Special Issue on Selected Papers from the Second International Workshop on Algorithms and Computation, WALCOM 2008 , Tome 13 (2009) no. 1, pp. 5-18 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

In this paper we give a simple algorithm to generate all connected rooted plane graphs with at most m edges. A rooted" plane graph is a plane graph with one designated (directed) edge on the outer face. The algorithm uses O(m) space and generates such graphs in O(1) time per graph on average without duplications. The algorithm does not output the entire graph but the difference from the previous graph. By modifying the algorithm we can generate all connected (non-rooted) plane graphs with at most m edges in O(m3) time per graph.
DOI : 10.7155/jgaa.00174
Keywords: algorithm, graph, listing, plane graph, family tree 
@article{JGAA_2009_13_1_a1,
     author = {Katsuhisa Yamanaka and Shin-ichi Nakano},
     title = {Listing {All} {Plane} {Graphs}},
     journal = {Journal of graph algorithms and applications},
     pages = {5--18},
     year = {2009},
     volume = {13},
     number = {1},
     doi = {10.7155/jgaa.00174},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00174/}
}
TY  - JOUR
AU  - Katsuhisa Yamanaka
AU  - Shin-ichi Nakano
TI  - Listing All Plane Graphs
JO  - Journal of graph algorithms and applications
PY  - 2009
SP  - 5
EP  - 18
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00174/
DO  - 10.7155/jgaa.00174
LA  - en
ID  - JGAA_2009_13_1_a1
ER  - 
%0 Journal Article
%A Katsuhisa Yamanaka
%A Shin-ichi Nakano
%T Listing All Plane Graphs
%J Journal of graph algorithms and applications
%D 2009
%P 5-18
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00174/
%R 10.7155/jgaa.00174
%G en
%F JGAA_2009_13_1_a1
Katsuhisa Yamanaka; Shin-ichi Nakano. Listing All Plane Graphs. Journal of graph algorithms and applications, 
							Special Issue on Selected Papers from the Second International Workshop on Algorithms and
Computation, WALCOM 2008
					, Tome 13 (2009) no. 1, pp. 5-18. doi: 10.7155/jgaa.00174

Cité par Sources :