Orthogonal graph drawing with inflexible edges
Orthogonal graph drawing with inflexible edges
复制标题
具有不灵活边缘的正交图绘制
DOI：
10.1016/j.comgeo.2016.03.001
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ignaz Rutter
中科院分区：
文献类型：
--
作者：
Thomas Bläsius;Sebastian Lehmann;Ignaz Rutter
我们考虑的问题，创建平面正交图纸的4-平面图（平面图的最大程度为4）与约束的弯曲每边的数量。更准确地说，我们有一个灵活性函数，为每条边e分配一个自然数flex（e），即它的灵活性。问题FlexDraw询问是否存在正交绘图，使得每个边e最多具有flex（e）弯曲。众所周知，如果对于每条边e [1]，flex（e）= 0，则FlexDraw是NP难的。另一方面，如果flex（e）≥ 1 [2]，则FlexDraw可以有效地求解，并且如果对于每条边e，flex（e）≥ 2 [3]则是平凡的。为了缩小flex（e）= 0的NP-困难和flex（e）≥ 1的有效算法之间的差距，我们研究了FlexDraw在只有少数边是不灵活的情况下的计算复杂性（即，具有灵活性0）。我们证明了对于任何ε> 0，FlexDraw对于具有O（n ε）个两两距离为Ω（n 1-ε）的非柔性边的例子是NP-完全的（包括它们诱导匹配的情况），其中n表示图中的顶点数。另一方面，我们给出了一个运行时间为O（2k <$n <$T flow（n））的FPT算法，其中T flow（n）是计算多源多汇平面流网络中最大流所需的时间，k是至少有一个端点为4度的非柔性边的个数.
We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e a natural number flex (e), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge e has at most flex (e) bends. It is known that FlexDraw is NP-hard if flex (e)= 0 for every edge e [1]. On the other hand, FlexDraw can be solved efficiently if flex (e)≥ 1 [2] and is trivial if flex (e)≥ 2 [3] for every edge e. To close the gap between the NP-hardness for flex (e)= 0 and the efficient algorithm for flex (e)≥ 1, we investigate the computational complexity of FlexDraw in case only few edges are inflexible (ie, have flexibility 0). We show that for any ε> 0 FlexDraw is NP-complete for instances with O (n ε) inflexible edges with pairwise distance Ω (n 1− ε)(including the case where they induce a matching), where n denotes the number of vertices in the graph. On the other hand, we give an FPT-algorithm with running time O (2 k⋅ n⋅ T flow (n)), where T flow (n) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4.
登录
查看更多内容
使用 SPQR 树在线维护三元连接组件
影响因子：
1.1
作者：
G. Battista;R. Tamassia
通讯作者：
R. Tamassia
具有凸弯曲成本的最优正交图绘制
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
正交图绘制的更好启发式
影响因子：
1.8
作者：
T. Biedl;G. Kant
通讯作者：
G. Kant
具有灵活性约束的正交图绘制
影响因子：
1.1
作者：
Thomas Bläsius;M. Krug;Ignaz Rutter;D. Wagner
通讯作者：
D. Wagner