路和圈的字典积在书中的嵌入（英文）

赵斌; 田应智; 孟吉翔

doi:10.13568/j.cnki.651094.2016.01.001

您当前的位置：

首页 >

文章列表页 >

路和圈的字典积在书中的嵌入（英文）

研究精粹 | 更新时间：2026-01-21

- 路和圈的字典积在书中的嵌入（英文）
- 路和圈的字典积在书中的嵌入（英文）
- 新疆大学学报（自然科学版中英文） 2016年33卷第1期页码：1-5
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  Supported by the Natural Science Foundation of China(11531011,11401510,11501487);the Key Laboratory Project of Xinjiang(2015KL019);the Doctoral Scientific Research Fund of Xinjiang University(BS150208)
- DOI：10.13568/j.cnki.651094.2016.01.001
  中图分类号： O157.5
- 纸质出版：2016
- 稿件说明：
移动端阅览
[1]赵斌,田应智,孟吉翔.路和圈的字典积在书中的嵌入（英文）[J].新疆大学学报(自然科学版),2016,33(01):1-5.
[1]赵斌,田应智,孟吉翔.路和圈的字典积在书中的嵌入（英文）[J].新疆大学学报(自然科学版),2016,33(01):1-5. DOI： 10.13568/j.cnki.651094.2016.01.001.

DOI：10.13568/j.cnki.651094.2016.01.001.

摘要

把一个图G嵌入到书中就是把G的顶点放到书脊上

各条边嵌入到一些半平面上并且保证同一个半平面内各条边不相交.在本文中

作者讨论了路和圈字典积的书式嵌入问题

并且给出了这些图书页数的上界.特别的

在某些条件下

作者给出了这些图确定的书页数.

Abstract

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges assigned to the same page without crossing.In this paper

we discuss book embedding of lexicographic product of paths and cycles

and give upper bounds of the page number of these graphs.Specially

in some conditions

we can determine the exact page number of these graphs.

关键词

Keywords

references

Ollmann L T.On the book thicknesses of various graphs[C]//Hoffman,Levow,T EDS Proc 4th southeastern conference on combinatorics,Graph theory and computing,Congressus Numerantium,Winnipeg:Utilitas Mathematics Publ Inc,1973.VIII 459.

Chung F R K,Leighton F T,Rosenberg A L.Embedding graph in books:a layout problem with applications to VLSI design[J].SIAM J Alg Disc Meth,1987,8(1):33-58.

Shahrokhi F,Shi W.On crossing sets,disjiont sets and pagenumber[J].J Algorithms,2000,34(1):40-53.

Rosenberg A L.The Diogenes approach to testable fault-tolerant arrays of processors[J].IEEE T Comput,1983,32(10):902-910.

Heath L S,Leighton F T,Rosenberg A L.Compariting queues and stacks as mechanisms for laying out graphs[J].SIAM J Discrete Math,1992,5(3):398-412.

Tarjan R E.Sorting using networks of queues and stacks[J].JACM,1972,19(2):341-346.

Bemhart F,Kainen B.The book thickness of a graph[J].J Comb Theory B,1979,27(3):320-331.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据