Placing Arrows in Directed Graph Drawings
We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic al
- PDF / 989,316 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 220 Views
Universit` a degli Studi di Perugia, Perugia, Italy {carla.binucci,walter.didimo,giuseppe.liotta, fabrizio.montecchiani}@unipg.it 2 Osnabr¨ uck University, Osnabr¨ uck, Germany [email protected]
Abstract. We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study.
1
Introduction
The default way of drawing a directed edge is to draw it as a line with an arrow head at its target. While there also exist other models (placing arrows at the middle, drawing edges in a “tapered” fashion, etc.; cf. [7,8]) the former is prevailing in virtually all software systems. However, this simple model becomes problematic when several edges attach to a vertex on a similar trajectory: it may be hard to see whether a specific edge is in- or outgoing, cf. Fig. 1 and [1]. We try to solve this issue by looking for a placement of the arrow heads such that (a) they do not overlap other edges or arrow heads, and (b) still retain the property of being at—or at least close to—the target vertices of the edges. In the following, we show NP-hardness of the problem, propose exact and heuristic algorithms for its discretized variant, and evaluate their practical performance in a brief exploratory study. We remark that our problem is related to map labeling and in particular to edge labeling problems [4,5,9–11,13,15–18]. For space reasons, some proofs and technical details are omitted in this extended abstract, and can be found in the appendix of the ArXiv version [1].
2
The Arrow Placement Problem
We first formally define our arrow placement problem and establish its theoretical time complexity. Let G = (V, E) be a digraph and let Γ be a straight-line drawing of G. We assume that in Γ each vertex v ∈ V is drawn as a circle Work is partially supported by the MIUR project AMANDA “Algorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT 001. c Springer International Publishing AG 2016 Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 44–51, 2016. DOI: 10.1007/978-3-319-50106-2 4
Placing Arrows in Directed Graph Drawings
45
Fig. 1. Layouts of a digraph with 10 vertices and 21 edges. (left) The arrows are placed by a common editor; several arrows overlap and the direction of, e.g., the thick red edge is not clear. (right) The arrows are placed by our exact method. (Color figure online)
(possibly a point) Cv . We also assume that, for each edge e ∈ E, the arrow of e is modeled as a circle Ce of positive radius, centered in a point along the segment that represents e: when Γ is displayed, the arrow of e is drawn as a triangle inscribed in Ce , suitably rotated according to the direction of e. We assume that all circles representing a vertex (arrow) have a common radius rV (rE , respectively). We say that two arrows—or an arrow and a vertex—overlap if their corresponding circles inters
Data Loading...
