Embeddings of graphs of fixed treewidth and bounded degree

被引：0

作者：

Gross, Jonathan L. ^{[1
]}

机构：

[1] Columbia Univ, Dept Comp Sci, New York, NY 10027 USA

来源：

ARS MATHEMATICA CONTEMPORANEA | 2014年 / 7卷 / 02期

关键词：

Genus distribution; partial genus distribution; treewidth; tree decomposition; GENUS DISTRIBUTION; DISTRIBUTIONS; ROOT;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：379 / 403

页数：25

共 28 条

[1] Beineke LW, 2009, ENCYCLOP MATH APPL, V128, P1, DOI 10.1017/CBO9781139087223
[2] A partial k-arboretum of graphs with bounded treewidth
Bodlaender, HL
[J]. THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) : 1 - 45
[3] A linear-time ie algorithm for finding three-decompositions of small treewidth
Bodlaender, HL
[J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (06) : 1305 - 1317
[4] Borie R. B., 2014, HDB GRAPH THEORY, P101
[5] GENUS DISTRIBUTIONS FOR 2 CLASSES OF GRAPHS
FURST, ML
GROSS, JL
STATMAN, R
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (01) : 22 - 36
[6] Gross J., 2001, Topological Graph Theory
[7] Gross J. L., 2013, GENUS DISTRIBUTION I
[8] Gross J.L., 2013, LOG CONCAVITY UNPUB
[9] Gross J. L., 2011, Journal of Graph Algorithms and Applications, V15, P295
[10] Gross JL, 2013, ARS MATH CONTEMP, V6, P37

← 1 2 3 →