2005年
An improved bound on the one-sided minimum crossing number in two-layered drawings
Discrete and Computational Geometry
- 巻
- 33
- 号
- 4
- 開始ページ
- 565
- 終了ページ
- 591
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00454-005-1168-0
- 出版者・発行元
- Springer New York
Given a bipartite graph G = (V,W,E), a two-layered drawing consists of placing nodes in the first node set V on a straight line L1 and placing nodes in the second node set W on a parallel line L2. The one-sided crossing minimization problem asks one to find an ordering of nodes in V to be placed on L1 so that the number of arc crossings is minimized. In this paper we use a 1.4664-approximation algorithm for this problem. This improves the previously best bound 3 due to P. Eades and N. C. Wormald [Edge crossing in drawing bipartite graphs, Algorithmica 11 (1994), 379-403]. © 2005 Springer Science+Business Media, Inc.
- ID情報
-
- DOI : 10.1007/s00454-005-1168-0
- ISSN : 0179-5376
- SCOPUS ID : 17444408938