Geodesic
Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 185-204.

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

In this article we define a canonical decomposition of rooted outerplanar maps into a spanning tree and a list of edges. This decomposition, constructible in linear time in the Word-RAM model, implies the existence of bijection between rooted outerplanar maps with n nodes and bicolored rooted ordered trees with n nodes where all the nodes of the last branch are colored white. As a consequence, for rooted outerplanar maps of n nodes, we derive: an enumeration formula, and an asymptotic of 23n −Θ(logn); an optimal data structure of asymptotically 3n bits, built in O(n) time, supporting adjacency and degree queries in worst-case constant time and neighbors query of a degree-d node in worst-case O(d) time. an O(n) expected time uniform random generating algorithm. 
@article{JGAA_2005_9_2_a0,
     author = {Nicolas Bonichon and Cyril Gavoille and Nicolas Hanusse},
     title = {Canonical {Decomposition} of {Outerplanar} {Maps} and {Application} to {Enumeration,} {Coding} and {Generation}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {185--204},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2005},
     doi = {10.7155/jgaa.00105},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00105/}
}
TY  - JOUR
AU  - Nicolas Bonichon
AU  - Cyril Gavoille
AU  - Nicolas Hanusse
TI  - Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
JO  - Journal of Graph Algorithms and Applications
PY  - 2005
SP  - 185
EP  - 204
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00105/
DO  - 10.7155/jgaa.00105
LA  - en
ID  - JGAA_2005_9_2_a0
ER  - 
%0 Journal Article
%A Nicolas Bonichon
%A Cyril Gavoille
%A Nicolas Hanusse
%T Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation
%J Journal of Graph Algorithms and Applications
%D 2005
%P 185-204
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00105/
%R 10.7155/jgaa.00105
%G en
%F JGAA_2005_9_2_a0
Nicolas Bonichon; Cyril Gavoille; Nicolas Hanusse. Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding and Generation. Journal of Graph Algorithms and Applications, Tome 9 (2005) no. 2, pp. 185-204. doi : 10.7155/jgaa.00105. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00105/

Cité par Sources :