Embeddings of graphs of fixed treewidth and bounded degree
Jonathan L. Gross · Ars Mathematica Contemporanea · 2013
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.