436 KB57 KB200820252014Gross, Jonathan L.številka:2letnik:7str. 379-403COBISSID:17064281ISSN:1855-3966URN:URN:NBN:SI:doc-4WJBEZXHenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneagenus distributionpartial genus distributiontree decompositiontreewidthEmbeddings of graphs of fixed treewidth and bounded degree|Let ?$\mathcal{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 ?$\mathcal{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 timeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije