MISC

査読有り
2008年

Approximating crossing minimization in radial layouts

LATIN 2008: THEORETICAL INFORMATICS
  • Seok-Hee Hong
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000254390900040&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • Web of Science ID : WOS:000254390900040

エクスポート
BibTeX RIS