Geodesic
Embeddings of cubic Halin graphs: Genus distributions
Ars Mathematica Contemporanea, Tome 6 (2013) no. 1, pp. 37-56.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

We derive an O(n2)-time algorithm for calculating the genus distribution of a given 3-regular Halin graph G; that is, we calculate the sequence of numbers g0(G), g1(G), g2(G), … on the respective orientable surfaces S0, S1, S2, …. Key topological features are a quadrangular decomposition of plane Halin graphs and a new recombinant-strands reassembly process that fits pieces together three-at-a-vertex. Key algorithmic features are reassembly along a post-order traversal, with just-in-time dynamic assignment of roots for quadrangular pieces encountered along the tour.
DOI : 10.26493/1855-3974.217.440
Keywords: Genus distribution, Halin graph, partitioned genus distribution, gram embedding, outerplanar graph, topological graph theory. 
@article{10_26493_1855_3974_217_440,
     author = {Jonathan L. Gross},
     title = {Embeddings of cubic {Halin} graphs: {Genus} distributions},
     journal = {Ars Mathematica Contemporanea},
     pages = {37--56},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2013},
     doi = {10.26493/1855-3974.217.440},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.217.440/}
}
TY  - JOUR
AU  - Jonathan L. Gross
TI  - Embeddings of cubic Halin graphs: Genus distributions
JO  - Ars Mathematica Contemporanea
PY  - 2013
SP  - 37
EP  - 56
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.217.440/
DO  - 10.26493/1855-3974.217.440
LA  - en
ID  - 10_26493_1855_3974_217_440
ER  - 
%0 Journal Article
%A Jonathan L. Gross
%T Embeddings of cubic Halin graphs: Genus distributions
%J Ars Mathematica Contemporanea
%D 2013
%P 37-56
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.217.440/
%R 10.26493/1855-3974.217.440
%G en
%F 10_26493_1855_3974_217_440
Jonathan L. Gross. Embeddings of cubic Halin graphs: Genus distributions. Ars Mathematica Contemporanea, Tome 6 (2013) no. 1, pp. 37-56. doi : 10.26493/1855-3974.217.440. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.217.440/

Cité par Sources :