We are interested in finding combinatorial criteria for embedding graphs into torus and using them in the embedding check algorithm. It is a well-known fact that any connected graph can be reduced to a one-vertex graph with loops and is homotopy equivalent to such a graph. If a connected graph has intersection of some edges, then some loops of one-vertex graph will also intersect. Therefore the problem of embedding graphs into some surface is equivalent to the question of embedding one-vertex graph in given surface. This paper considers a graph with rotations or rotation system called hieroglyph. The equivalence of four conditions is proved: (1) embedding hieroglyph into torus; (2) the absence of forbidden subgraphs in a hieroglyph; (3) some condition for the graph of loops; (4) the existence of a reduction of hieroglyph to one of the list of hieroglyphs. We also prove the existence of an algorithm with complexity $O(n)$ that recognizes embedding hieroglyph into torus.


翻译:我们有兴趣找到将图形嵌入横纹体并用于嵌入检查算法的组合标准。 众所周知, 任何连接的图形都可以压缩为带环的一面形图, 并且具有等同该图形的同质性。 如果连接的图形具有某些边缘的交叉点, 那么一些一面形图的循环也会相互交错。 因此, 将图形嵌入某些表面的问题相当于将一面图嵌入给定表面的问题。 本文考虑一个带有旋转或旋转系统的图表, 叫做象形体。 四个条件的等值已被证明:(1) 将象形形体嵌入图中;(2) 象形形图中缺少被禁止的子图;(3) 圆形图中的某些条件;(4) 将象形体缩小到象形体列表中的一个。 我们还证明存在一个复杂度为$( n)美元的算法, 承认将象形体嵌入象形体到象形体中。

0
下载
关闭预览

相关内容

NeurlPS 2022 | 自然语言处理相关论文分类整理
专知会员服务
48+阅读 · 2022年10月2日
Artificial Intelligence: Ready to Ride the Wave? BCG 28页PPT
专知会员服务
26+阅读 · 2022年2月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
240+阅读 · 2020年4月19日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
144+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
169+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
会议交流 | IJCKG: International Joint Conference on Knowledge Graphs
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年10月4日
Arxiv
20+阅读 · 2021年9月22日
VIP会员
相关VIP内容
NeurlPS 2022 | 自然语言处理相关论文分类整理
专知会员服务
48+阅读 · 2022年10月2日
Artificial Intelligence: Ready to Ride the Wave? BCG 28页PPT
专知会员服务
26+阅读 · 2022年2月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
240+阅读 · 2020年4月19日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
144+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
169+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
会议交流 | IJCKG: International Joint Conference on Knowledge Graphs
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员