平面图的书式嵌入

论文摘要

图的书式嵌入是将节点按顺序排在一条直线上（书脊）且将边嵌入以书脊为边界的半平面上（页）使得嵌入同页中的边互不相交.该理论起源于诸多领域,例如:并行处理,容错处理器的分配,有向互联网,大型集成电路设计（VLSI）等,其研究成果尤其有助于计算机的发展.因此图的书式嵌入有广泛的应用背景.如果图G可使得边互不交叉的画在平面上,则称图G为平面图.最大度为k的平面图为平面k-图.如果图G可每边至多交叉一次的画到平面上,则称图G为1-平面图.针对书式嵌入问题,本文主要研究平面5-图和1-平面图并得出以下两个结论:1.用类似于Bekos[M.A.Bekkos,M.Gronemann,and C.N.Raftopulou,Two-page book embeddifngs of 4-planar graphs,31st Symposium on Theoretical Aspects of Computer Science（2014）137-148]的算法,给出平面5-图可嵌入3页书中的二次算法.2.通过改进Alam[M.J.Alam,F.Brandenburg,and S.Kobourov,On the Book Thickness of 1-Planar Graphs,arXiv:1510.05891]的算法,给出3-连通1-平面图可嵌入9页书中的线性算法,进一步,给出1-平面图可嵌入13页书中的线性算法。

论文目录

文章来源

类型: 硕士论文

作者: 关夏夏

导师: 杨卫华

关键词: 书式嵌入,平面图,页数,交叉

来源: 太原理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 太原理工大学

分类号: O157.5

总页数: 54

文件大小: 3849K

下载量: 18

相关论文文献

• [1].作为说书式“叙述者”的教师——论高校文学史课堂叙事化教学中的教师角色功能[J]. 当代教育理论与实践 2020(02)
• [2].前沿资讯[J]. 阅读 2016(88)
• [3].基于信息素养培养的信息技术学科定位与早期的软件说明书式教学的区别[J]. 学园 2017(07)
• [4].陆天奕的作品[J]. 艺术百家 2015(06)
• [5].书式生活,与优雅有关[J]. 中华民居(上旬版) 2012(09)
• [6].阶为奇且连通的双环网络的书式嵌入(英文)[J]. 新疆大学学报(自然科学版) 2011(02)
• [7].基于“学为中心”板书式历史课堂的构建[J]. 天津教育 2020(26)
• [8].一次补正商品名称的利与弊[J]. 中华商标 2015(02)
• [9].平面图书式嵌入综述[J]. 数学进展 2020(01)
• [10].整合有道——《猴王出世》教学设计[J]. 中国信息技术教育 2012(02)
• [11].打造暑期教师的丰富表情[J]. 青年教师 2010(08)
• [12].青番茄:网上免费图书馆[J]. 互联网天地 2011(04)
• [13].2015商标申请书式培训班在广州举办[J]. 中华商标 2015(06)
• [14].健全责任体系 做实政治巡察“后半篇文章”[J]. 四川党的建设 2018(06)
• [15].“大南方大陆号”船长的有趣收藏——访英国玻璃艺术家詹姆斯·马斯克里[J]. 中国文艺家 2019(05)
• [16].学校安全治理要在薄弱点发力[J]. 教学管理与教育研究 2019(24)
• [17].闻一多“类书式的诗”论述评[J]. 聊城大学学报(社会科学版) 2017(04)
• [18].享受“书式”生活[J]. 幸福 2018(10)
• [19].冀南银行“背书式”套票样[J]. 中国钱币 2009(02)
• [20].走进“悦读”世界,享受“书式”生活[J]. 图书馆杂志 2009(07)
• [21].路和圈的半强积在书中的嵌入（英文）[J]. 湖南师范大学自然科学学报 2015(06)
• [22].007不好当[J]. 中国药店 2013(18)
• [23].网络时代的“书式”生活[J]. 广东第二课堂(中学生阅读) 2011(Z2)
• [24].浅评电视新闻的新形式[J]. 内江科技 2011(11)
• [25].论提高动手能力与拓展PLC设计水平[J]. 中国市场 2016(23)
• [26].新疆:进一步完善食品安全电子监管网络建设[J]. 工商行政管理 2009(10)
• [27].“青番茄”和她的小清新阅读时代[J]. 新青年(珍情) 2012(01)
• [28].写作能力的提高从感悟起步[J]. 新作文(中学作文教学研究) 2010(Z2)
• [29].路和圈的字典积在书中的嵌入（英文）[J]. 新疆大学学报(自然科学版) 2016(01)
• [30].商标注册网上申请填写要求[J]. 中华商标 2009(02)

标签：书式嵌入论文;  平面图论文;  页数论文;  交叉论文;