On the one-sided crossing minimization in a bipartite graph with large degrees

作     者：Nagamochi, H 

作者机构：Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2005年第332卷第1-3期

页      面：417-446页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministry of Education  Culture  Sports  Science and Technology  MEXT 

主　　题：approximation algorithm bipartite graph edge crossing graph drawing 2-layered drawing randomized algorithm 

摘      要：Given a bipartite graph G = (V, W, E), a 2-layered drawing consists of placing nodes in the first node set V on a straight line L-1 and placing nodes in the second node set Won a parallel line L-2. For a given ordering of nodes in Won L2, the one-sided crossing minimization problem asks to find an ordering of nodes in V on L-1 so that the number of arc crossings is minimized. A well-known lower bound LB on the minimum number of crossings is obtained by summing up min{c(uv), c(vu)} over all node pairs u, v is an element of V, where c(uv) denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most (1.2964 + 12/(delta - 4))LB if the minimum degree delta of a node in V is at least 5. (c) 2004 Elsevier B.V. All rights reserved.