Approximating Crossing Minimization in Radial Layouts
Approximating Crossing Minimization in Radial Layouts
复制标题
径向布局中的近似交叉最小化
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
H. Nagamochi
中科院分区：
文献类型：
--
作者：
Seok;H. Nagamochi
研究了一个具有两轨道径向布局的二部图的交叉最小化问题。放射状布局在社交网络可视化中有很强的应用，可以显示参与者的中心性。如果两个轨道中有一个轨道上的顶点位置是固定的，这个问题被称为单侧交叉最小化，并且已知是np困难的。提出了一种近似算法，证明了径向布局的单侧交叉最小化是15近似的。
We study a crossing minimization problem of drawing a bipartite graph with a radial layout of two orbits. Radial layouts have strong application in social network visualization, displaying centrality of actors. The problem is called the one-sided crossing minimization if the positions of vertices in one of the two orbits are fixed, and is known to be NP-hard. We present the first approximation algorithm, proving that the one-sided crossing minimization in a radial layout is 15-approximable.