For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 An Exact Algorithm for the Arrow Placement Problem in Directed Graph DrawingsNaoto KIDO  Sumio MASUDA  Kazuaki YAMAGUCHI  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.11   pp.1481-1489Publication Date: 2019/11/01 Online ISSN: 1745-1337 DOI: 10.1587/transfun.E102.A.1481 Type of Manuscript: PAPERCategory: Algorithms and Data StructuresKeyword: directed graph,  drawing,  arrow placement,  exact algorithm,  Full Text: PDF(1.1MB)>> Buy this Article Summary:  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.