The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kami menganggap masalah meletakkan anak panah, yang menunjukkan arah setiap tepi dalam lukisan graf terarah, tanpa menjadikannya bertindih dengan anak panah, bucu dan tepi lain sebanyak mungkin. Dua kaedah berikut telah dicadangkan untuk masalah ini. Satu ialah algoritma yang tepat untuk kes di mana kedudukan setiap anak panah dihadkan kepada beberapa titik diskret. Yang lain ialah algoritma heuristik untuk kes di mana anak panah dibenarkan bergerak secara berterusan pada setiap tepi. Dalam makalah ini, kami menganggap bahawa kedudukan anak panah tidak terhad kepada titik diskret dan mencadangkan algoritma yang tepat untuk masalah mencari peletakan anak panah supaya (a) jumlah wajaran bilangan pertindihan dengan tepi, bucu dan anak panah lain adalah diminimumkan dan (b) jumlah jarak antara anak panah dan bucu terminal tepinya diminimumkan sebagai objektif kedua. Kaedah yang dicadangkan menyelesaikan masalah ini dengan mengurangkannya kepada masalah pengaturcaraan linear integer bercampur. Oleh kerana ini ialah algoritma masa eksponen, kami menambah prosedur mudah sebagai prapemprosesan untuk mengurangkan masa berjalan. Keputusan eksperimen menunjukkan bahawa kaedah yang dicadangkan boleh mencari peletakan anak panah yang lebih baik daripada kaedah sebelumnya dan prosedur untuk mengurangkan masa berjalan adalah berkesan.
Naoto KIDO
Kobe University
Sumio MASUDA
Kobe University
Kazuaki YAMAGUCHI
Kobe University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Naoto KIDO, Sumio MASUDA, Kazuaki YAMAGUCHI, "An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 11, pp. 1481-1489, November 2019, doi: 10.1587/transfun.E102.A.1481.
Abstract: We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1481/_p
Salinan
@ARTICLE{e102-a_11_1481,
author={Naoto KIDO, Sumio MASUDA, Kazuaki YAMAGUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings},
year={2019},
volume={E102-A},
number={11},
pages={1481-1489},
abstract={We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.},
keywords={},
doi={10.1587/transfun.E102.A.1481},
ISSN={1745-1337},
month={November},}
Salinan
TY - JOUR
TI - An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1481
EP - 1489
AU - Naoto KIDO
AU - Sumio MASUDA
AU - Kazuaki YAMAGUCHI
PY - 2019
DO - 10.1587/transfun.E102.A.1481
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2019
AB - We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.
ER -