1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman's result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm et al.


翻译:1-平面图是可在平面上绘制的图表,可以使任何边缘与其他边缘相交。 Ackerman 显示, 1-平面图的边缘可以分割成平面图和森林,并声称证据会导致线性时间算法。然而,尚不清楚如何从他的证据中获得这样的算法。在本文中,我们首先对Ackerman的结果进行重新论证(事实上,我们证明这是一个略微笼统的说明),然后通过使用Holm 等人的边缘合同数据结构来显示分割在线性时间。

0
下载
关闭预览

相关内容

专知会员服务
84+阅读 · 2020年12月5日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
17篇知识图谱Knowledge Graphs论文 @AAAI2020
专知会员服务
171+阅读 · 2020年2月13日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
17篇必看[知识图谱Knowledge Graphs] 论文@AAAI2020
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
5+阅读 · 2019年4月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年6月15日
Arxiv
0+阅读 · 2021年4月2日
Directional Graph Networks
Arxiv
27+阅读 · 2020年12月10日
VIP会员
相关VIP内容
相关资讯
AAAI2020 图相关论文集
图与推荐
10+阅读 · 2020年7月15日
17篇必看[知识图谱Knowledge Graphs] 论文@AAAI2020
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
5+阅读 · 2019年4月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员