Embeddings of graphs of fixed treewidth and bounded degree

作者：Gross Jonathan L^*

来源：Ars Mathematica Contemporanea, 2014, 7(2): 379-403.

• Genus distribution
• partial genus distribution
• treewidth
• tree decomposition

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.

• 出版日期2014