2008年
Approximating crossing minimization in radial layouts
LATIN 2008: THEORETICAL INFORMATICS
- ,
- 巻
- 4957
- 号
- 開始ページ
- 461
- 終了ページ
- +
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
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.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000254390900040