Approximating the Maximum Rectilinear Crossing Number
Approximating the Maximum Rectilinear Crossing Number
复制标题
近似最大直线交叉数
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ou Liu
中科院分区：
文献类型：
--
作者：
S. Bald;Matthew P. Johnson;Ou Liu
以一种最小化交叉次数的方式绘制图形是一个经过充分研究的问题。最近，在假设直线（直线）边的情况下，对各种图类中可能的最小和最大交叉数进行了刻画。在本文中，我们研究了在一个图形的所有直线图上，使相交边的数目最大化的算法问题。我们证明了这个问题是np困难的，并且存在于（exists mathbb {R}）。本文给出了自然随机化1/3近似算法的非平凡非随机化，该算法推广到一个加权集合和一个排序约束满足问题。我们在模拟中评估了这些算法和其他启发式算法。
Drawing a graph in a way that minimizes the number of edge-crossings is a well-studied problem. Recently there has been work characterizing both the minimum and maximum number of edge-crossings possible in various graph classes, assuming rectilinear (straight-line) edges. In this paper, we investigate the algorithmic problem of maximizing the number of edge-crossings over all rectilinear drawings a graph. We show that this problem is NP-hard and lies in (exists mathbb {R}). We give a nontrivial derandomization of the natural randomized 1/3-approximation algorithm, which generalizes to a weighted setting as well as to an ordering constraint satisfaction problem. We evaluate these algorithms and other heuristics in simulation.