We consider the problem of drawing an outerplanar graph with $n$ vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it can be decided in $O(nm)$ time if such a drawing exists, where $m\le n-3$ is the number of interior edges. In the positive case, we can also compute such a drawing.


翻译:我们认为,如果外表已经作为一个简单的多边形被画成,则绘制外平面图的问题就在于,如果外平面已经作为一个简单的多边形,则外平面最多有一个弯曲的圆顶值为一美元。我们证明,如果有这样的图画,可以用O(nm)美元的时间来决定,其中内平面数是$m\le n-3美元。在正面的例子中,我们也可以计算出这样的图画。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2021年8月8日
专知会员服务
31+阅读 · 2021年7月15日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
180+阅读 · 2020年4月26日
因果图,Causal Graphs,52页ppt
专知会员服务
241+阅读 · 2020年4月19日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
101+阅读 · 2019年10月9日
【ICLR2020】五篇Open代码的GNN论文
专知会员服务
47+阅读 · 2019年10月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年10月17日
Arxiv
0+阅读 · 2021年10月15日
Arxiv
0+阅读 · 2021年9月22日
Explanatory Graphs for CNNs
Arxiv
4+阅读 · 2018年12月18日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2021年8月8日
专知会员服务
31+阅读 · 2021年7月15日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
180+阅读 · 2020年4月26日
因果图,Causal Graphs,52页ppt
专知会员服务
241+阅读 · 2020年4月19日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
101+阅读 · 2019年10月9日
【ICLR2020】五篇Open代码的GNN论文
专知会员服务
47+阅读 · 2019年10月2日
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Top
微信扫码咨询专知VIP会员