Let F be any family of graphs of fixed treewidth and bounded degree. We construct a quadratic-time algorithm for calculating the genus distribution of the graphs in F. Within a post-order traversal of the decomposition tree, the algorithm involves a full-powered upgrading of production rules and root-popping. This algorithm for calculating genus distributions in quadratic time complements an algorithm of Kawarabayashi, Mohar, and Reed for calculating the minimum genus of a graph of bounded treewidth in linear time.
@article{366, title = {Embeddings of graphs of fixed treewidth and bounded degree}, journal = {ARS MATHEMATICA CONTEMPORANEA}, volume = {6}, year = {2013}, doi = {10.26493/1855-3974.366.dd1}, language = {EN}, url = {http://dml.mathdoc.fr/item/366} }
Gross, Jonathan L. Embeddings of graphs of fixed treewidth and bounded degree. ARS MATHEMATICA CONTEMPORANEA, Tome 6 (2013) . doi : 10.26493/1855-3974.366.dd1. http://gdmltest.u-ga.fr/item/366/