2005年2月
On the one-sided crossing minimization in a bipartite graph with large degrees
THEORETICAL COMPUTER SCIENCE
- 巻
- 332
- 号
- 1-3
- 開始ページ
- 417
- 終了ページ
- 446
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2004.10.042
- 出版者・発行元
- ELSEVIER SCIENCE BV
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.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.tcs.2004.10.042
- DBLP
- https://dblp.uni-trier.de/rec/journals/tcs/Nagamochi05
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000227578800020&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/tcs/tcs332.html#journals/tcs/Nagamochi05
- ID情報
-
- DOI : 10.1016/j.tcs.2004.10.042
- ISSN : 0304-3975
- DBLP ID : journals/tcs/Nagamochi05
- Web of Science ID : WOS:000227578800020