Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
复制标题
康定斯基模型中高级正交图嵌入的复杂性
DOI：
10.1007/978-3-662-44777-2_14
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Ignaz Rutter
中科院分区：
文献类型：
--
作者：
Thomas Bläsius;Guido Brückner;Ignaz Rutter
我们证明了在所谓的Kandinsky模型（允许度> 4的顶点）中寻找具有最小弯曲数的平面图（具有固定组合嵌入的平面图）的正交网格嵌入是NP完全的，从而解决了一个长期存在的公开问题。在积极的一面，我们给出了一个有效的算法的几个限制性的变种，如图的有界分支宽度和一般平面图的次指数精确算法。
We show that finding orthogonal grid embeddings ofplane graphs(planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (allowing vertices of degree > 4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.
登录
查看更多内容
具有凸弯曲成本的最优正交图绘制
DOI：
10.1145/2838736
发表时间：
2016
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Thomas Bläsius;Ignaz Rutter;Dorothea Wagner
通讯作者：
Dorothea Wagner
加速弯曲最小化
DOI：
--
发表时间：
2011
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Sabine Cornelsen;Andreas Karrenbauer
通讯作者：
Andreas Karrenbauer
平面图可分解性和固定参数算法的新上限
DOI：
--
发表时间：
2002
期刊：
影响因子：
--
作者：
F. Fomin;D. Thilikos
通讯作者：
D. Thilikos
UML 类图的自动布局：拓扑-形状-度量方法
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
Markus Eiglsperger
通讯作者：
Markus Eiglsperger
正交图绘制的更好启发式
影响因子：
1.8
作者：
T. Biedl;G. Kant
通讯作者：
G. Kant