Research on the Embedding graphs in Two-page books

摘要：

We study the VLSI-related problem of embedding graphs in books. A blacklwhite (b/w) book embedding of a b/w graph (G,U) is a book embedding of G, where the vertices of U are placed consecutively on the spine. In this paper we prove that every b/w tree admits a two-page b/w embedding. The proof takes the form of a linear time algorithm, which uses an extension of the unfolding technique.

关键词： Embedding graphs Two-page b/w graph

作者: WANG Xiao-Li

作者单位: College of Economic & Management.Zhongyuan University of Technology.Zhengzhou 450007, China

会议类型: 国际会议

会议名称: 2009 WASE International Conference on Information Engineering(2009年国际信息工程会议)(ICIE 2009)

会议地点: 太原

会议语种:英文

页码: 232-235

在线出版日期: 2009-07-10（万方平台首次上网日期，不代表论文的发表时间）