有向グラフ描画における矢印配置問題のための正確なアルゴリズム

KIDO Naoto; MASUDA Sumio; YAMAGUCHI Kazuaki

文献

J-GLOBAL ID：202002265270255907 整理番号：20A0107092

有向グラフ描画における矢印配置問題のための正確なアルゴリズム

An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A0107092&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A0107092&from=J-GLOBAL&jstjournalNo=U0466A") }}

著者 (3件)： , ,
資料名：
巻： E102.A 号： 11 ページ： 1481-1489(J-STAGE) 発行年： 2019年
JST資料番号： U0466A ISSN： 1745-1337 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

著者らは,有向グラフ描画の各エッジの方向を示す矢印を,出来るだけ多く他の矢印,頂点およびエッジと重ならないで配置する問題を検討した。この問題に対して,次の2つの方法を提案した。1つは,各矢印の位置がいくつかの離散点に制限される場合のための正確なアルゴリズムであった。もう1つは,矢印が各エッジ上で連続的に移動できる場合のための発見的アルゴリズムであった。本論文では,著者らは矢印の位置が離散点に制限されないと仮定し,そして(a)エッジ,頂点およびその他の矢印との重複数の加重和を最小化し(b)矢印とそれらのエッジ終端頂点間の距離の和を二次目的として最小化するよう,矢印配置を見つける問題のための正確なアルゴリズムを提案した。提案した方法は,それを混合整数線形計画問題に低減することによりこの問題を解決した。これは指数時間アルゴリズムであるので,著者らは実行時間を短縮するための前処理として簡単な手順を追加した。実験結果は,提案した方法が以前の方法よりも優れた矢印配置を見つけることができ,そして実行時間を減らすための手順が効果的であることを示した。(翻訳著者抄録)

, , , , , , , , , ,
, ,

著者キーワード (4件)： , , ,

図形・画像処理一般

引用文献 (12件)：

[1] R. Tamassia ed., Handbook of Graph Drawing and Visualization, CRC Press, Boca Raton, FL, 2014.
[2] P. Eades, “A heuristics for graph drawing,” Congressus Numerantium, vol.42, pp.146-160, 1984.
[3] T. Kamada and S. Kawai, “An algorithm for drawing general undirected graphs,” Inform. Process. Lett., vol.31, no.1, pp.7-15, 1989. 10.1016/0020-0190(89)90102-6
[4] C. Binucci, M. Chimani, W. Didimo, G. Liotta, and F. Montecchiani, “Placing arrows in directed graph drawings,” Proc. 24th Int'l Symp. on Graph Drawing and Network Visualization, Lect. Notes Comput. Sci., vol.9801, pp.44-51, Springer, Berlin, 2016. (full paper version: http://arxiv.org.abs.1608.08505v1)
[5] G. Neyer, “Map labeling with application to graph drawing,” Drawing Graphs, M. Kaufmann and D. Wagner, eds., Lect. Notes Comput. Sci., vo.2025, pp.247-273, Springer, Berlin, 2001. 10.1007/3-540-44969-8_10

, , , ,

前のページに戻る