Geodesic
Genus Distributions of Cubic Outerplanar Graphs
Journal of graph algorithms and applications, Tome 15 (2011) no. 2, pp. 295-316 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We present a quadratic-time algorithm for computing the genus distribution of any 3-regular outerplanar graph. Although recursions and some formulas for genus distributions have previously been calculated for bouquets and for various kinds of ladders and other special families of graphs, cubic outerplanar graphs now emerge as the most general family of graphs whose genus distributions are known to be computable in polynomial time. The key algorithmic features are the syntheses of the given outerplanar graph by a sequence of edge-amalgamations of some of its subgraphs, in the order corresponding to the post-order traversal of a plane tree that we call the inner tree, and the coordination of that synthesis with just-in-time root-splitting. 
@article{JGAA_2011_15_2_a5,
     author = {Jonathan Gross},
     title = {Genus {Distributions} of {Cubic} {Outerplanar} {Graphs}},
     journal = {Journal of graph algorithms and applications},
     pages = {295--316},
     year = {2011},
     volume = {15},
     number = {2},
     doi = {10.7155/jgaa.00227},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00227/}
}
TY  - JOUR
AU  - Jonathan Gross
TI  - Genus Distributions of Cubic Outerplanar Graphs
JO  - Journal of graph algorithms and applications
PY  - 2011
SP  - 295
EP  - 316
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00227/
DO  - 10.7155/jgaa.00227
LA  - en
ID  - JGAA_2011_15_2_a5
ER  - 
%0 Journal Article
%A Jonathan Gross
%T Genus Distributions of Cubic Outerplanar Graphs
%J Journal of graph algorithms and applications
%D 2011
%P 295-316
%V 15
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00227/
%R 10.7155/jgaa.00227
%G en
%F JGAA_2011_15_2_a5
Jonathan Gross. Genus Distributions of Cubic Outerplanar Graphs. Journal of graph algorithms and applications, Tome 15 (2011) no. 2, pp. 295-316. doi: 10.7155/jgaa.00227

Cité par Sources :