首页> 外文期刊>Algorithmica >Approximation Algorithms for Minimizing Edge Crossings in Radial Drawings
【24h】

Approximation Algorithms for Minimizing Edge Crossings in Radial Drawings

机译:最小化径向图中边缘交叉的近似算法

获取原文
获取原文并翻译 | 示例

摘要

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. Graph. 13, 583–594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.
机译:我们研究了用两个轨道的径向图绘制二部图的交叉最小化问题。径向绘图是社交网络分析和可视化中众所周知的绘​​图惯例之一,尤其是显示参与者的中心指数(Wasserman和Faust,《社交网络分析:方法和应用》,剑桥大学出版社,剑桥,1994年)。如果外部轨道的顶点位置固定,则本文的主要问题称为单边径向交叉最小化。已知该问题是NP难题(Bachmaier,IEEE Trans。Vis。Comput。Graph。13,583–594,2007),并且有许多启发式方法(Bachmaier,IEEE Trans。Vis。Comput。Graph。13)。 ,583–594,2007年)。但是,对于径向图中的交叉最小化问题,没有近似算法。针对单边径向交叉最小化问题,我们提出了第一个多项式时间常数因子近似算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号