One Sided Crossing Minimization Is NP-Hard for Sparse Graphs
One Sided Crossing Minimization Is NP-Hard for Sparse Graphs
复制标题
对于稀疏图，单边交叉最小化是 NP 困难的
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
I. Vrto
中科院分区：
文献类型：
--
作者：
X. Muñoz;Walter Unger;I. Vrto
单边交叉最小化问题包括将二部图的一个部分的顶点放置在直线上的指定位置上，并找到第二部分的顶点在平行线上的位置并将边绘制为直线，使得成对边交叉的数量最小化。该问题代表了用于美观地绘制分层图或生成基于行的 VLSI 布局的基本构建块。 Eades 和 Wormald [3] 表明该问题对于稠密图来说是 NP 困难的。具有实际意义的典型图表通常非常稀疏。我们证明，即使对于 4 星森林，这个问题仍然是 NP 困难的。
The one sided crossing minimization problem consists of placing the vertices of one part of a bipartite graph on prescribed positions on a straight line and finding the positions of the vertices of the second part on a parallel line and drawing the edges as straight lines such that the number of pairwise edge crossings is minimized. This problem represents the basic building block used for drawing hierarchical graphs aesthetically or producing row-based VLSI layouts. Eades and Wormald [3] showed that the problem is NP-hard for dense graphs. Typical graphs of practical interest are usually very sparse. We prove that the problem remains NP-hard even for forests of 4-stars.