On the pagenumber of the cube-connected cycles

被引：2

作者：

Tanaka Y. ^{[1
]}

Shibata Y. ^{[2
]}

机构：

[1] Information Science Center, Kyushu Institute of Technology, Kitakyushu, Fukuoka 804-8550, 1-1 Sensui-cho, Tobata-ku

[2] Department of Computer Science, Graduate School of Engineering, Gunma University, Kiryu, Gunma 376-8515

来源：

Mathematics in Computer Science | 2010年 / 3卷 / 1期

关键词：

Book embedding; Cube-connected cycles;

D O I：

10.1007/s11786-009-0012-y

中图分类号：

学科分类号：

摘要：

In this manuscript, we treat the book embedding of the cube-connected cycles. The book embedding of graphs is one of the graph layout problems and has been studied widely. We show that the pagenumber of CCC(n), n ≥ 4, is three and that of CCC(3) is two. This result is optimal since CCC(n) can not be embedded into two pages for n ≥ 4. © 2009 Birkhäuser Verlag Basel/Switzerland.

引用

页码：109 / 117

页数：8

共 9 条

[1]

Chartrand G., Lesniak L., Graphs & Digraphs, (2004)

[2]

Chung F.R.K., Leighton F.T., Rosenberg A.L., Embedding graphs in books: A layout problem with application to VLSI design, SIAM J. Algebraic Discret. Methods, 8, pp. 33-58, (1987)

[3]

Dujmovic V., Wood D.R., Stacks, queues and tracks: Layouts of graph subdivisions, Discret. Math. Theor. Comput. Sci., 7, pp. 155-202, (2005)

[4]

Hasunuma T., Embedding iterated line digraphs in books, Networks, 40, 2, pp. 51-62, (2002)

[5]

Konoe M., Hagiwara K., Tokura N., On the pagenumber of hypercubes and cube-connected cycles, IEICE Trans, J71-D, 3, pp. 490-500, (1988)

[6]

Muder D.J., Weaver M.L., West D.B., Pagenumber of complete bipartite graphs, J. Graph Theory, 12, pp. 469-489, (1988)

[7]

Preparata F.P., Vuillemin J., The cube-connected cycles: A versatile network for parallel computation, Commun. ACM, 24, 5, pp. 300-309, (1981)

[8]

Tanaka Y., Shibata Y., On the pagenumber of trivalent Cayley graphs, Discret. Appl. Math., 154, pp. 1279-1292, (2006)

[9]

Yannakakis M., Four pages are necessary and sufficient for planar graphs, Proceedings of 18th ACM symposium on theory of computing, pp. 104-108, (1986)

← 1 →