Embeddings of graphs of fixed treewidth and bounded degree
Gross, Jonathan L.
ARS MATHEMATICA CONTEMPORANEA, Tome 6 (2013), / Harvested from ARS MATHEMATICA CONTEMPORANEA
link
link
link

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.

Publié le : 2013-01-01
DOI : https://doi.org/10.26493/1855-3974.366.dd1 
@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/