We study the long-standing open problem of efficiently testing rectilinear planarity of series-parallel graphs (SP-graphs) in the variable embedding setting. A key ingredient behind the design of a linear-time testing algorithm for SP-graphs of vertex-degree at most three is that one can restrict the attention to a constant number of ``rectilinear shapes'' for each series or parallel component. To formally describe these shapes the notion of spirality can be used. This key ingredient no longer holds for SP-graphs with vertices of degree four, as we prove a logarithmic lower bound on the spirality of their components. The bound holds even for the independent-parallel SP-graphs, in which no two parallel components share a pole. Nonetheless, by studying the spirality properties of the independent-parallel SP-graphs, we are able to design a linear-time rectilinear planarity testing algorithm for this graph family.


翻译:我们研究了在变量嵌入设置中有效测试系列单线图(SP-graphs)的直线性平面图(SP-graphs)长期存在的开放问题。设计SP顶部分层图的线性时间测试算法背后的一个关键要素是,人们可以将注意力限制在每个序列或平行组件的“正线形形状”的恒定数上。要正式描述这些形状,可以使用螺旋性概念。这个关键成分不再用于具有四度顶部的 SP-graphs(SP-graphs),因为我们证明其组件的螺旋性对数约束较低。即使对于独立的单线性SP-graphs, 也没有两个平行组件共享一个极。然而,通过研究独立的单线SP-graphs的螺旋性特性,我们可以为这个图形家族设计一个线性直线性对线性平线性平线性测算算算法。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【2020新书】Web应用安全,331页pdf
专知会员服务
23+阅读 · 2020年10月24日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
0+阅读 · 2021年11月24日
Arxiv
0+阅读 · 2021年11月23日
On Sparsity Awareness in Distributed Computations
Arxiv
0+阅读 · 2021年11月23日
Arxiv
49+阅读 · 2021年5月9日
Arxiv
3+阅读 · 2018年10月25日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
7+阅读 · 2018年1月30日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
0+阅读 · 2021年11月25日
Arxiv
0+阅读 · 2021年11月24日
Arxiv
0+阅读 · 2021年11月23日
On Sparsity Awareness in Distributed Computations
Arxiv
0+阅读 · 2021年11月23日
Arxiv
49+阅读 · 2021年5月9日
Arxiv
3+阅读 · 2018年10月25日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
7+阅读 · 2018年1月30日
Top
微信扫码咨询专知VIP会员