Embeddings of graphs of fixed treewidth and bounded degree

Jonathan L. Gross


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.


Genus distribution, partial genus distribution, treewidth, tree decomposition

Full Text:


DOI: https://doi.org/10.26493/1855-3974.366.dd1

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications