1 Introduction
The partial edge drawing (PED) of a graph is a variation of a nodelink diagram that is a visual representation of a graph. In PED, a link is drawn, which is a partial visual representation of an edge; that is, a part of the link is omitted, and then intersections of links are eliminated. Therefore, PED can reduce visual clutter of nodelink diagrams. An experimental evaluation by Bruckdorfer et al. shows that PEDs reduces errors and provides higher accuracy when reading graphs than traditional nodelink diagrams; however, longer reading time is required [6].
We propose a morphing edge drawing (MED), which is a PED that changes with time. In MED, links are morphed between partial and complete drawings. Therefore, reduced loads are expected to infer undrawn parts in a PED. However, the effect depends on the scheduling of morphing edges. We designed a scheduling algorithm that did not unnecessarily cause links to cross. Then, we performed a user study to evaluate the effectiveness of MEDs by implementation. The contributions herein are as follows: Proposal and formalization of MED. Setting scheduling requirements. Proposal of algorithm for scheduling morphing. Evaluation of MED via user study.
2 Partial Edge Drawing
Let be a simple undirected graph and let be a drawing of , where and . Let be a traditional straightline drawing. Let the drawing of a node be a small disk placed at a position and let of an edge be a straightline segment between two nodes (disks) incident to the edge. That is, when . We call a complete edge drawing (CED) because it draws every straightline representing an edge completely.
We express the partial drawing of an edge as a function shown in Exp. (1).
(1) 
That is, of edge comprise the parts that remain after removing the corresponding parts from when the entire corresponds to the interval . Each of the remaining continuous parts is called a stub. The parameters and , which determine the stub lengths, are partial edge parameters. When and for , the part to be deleted is not the end of ; two stubs remain at the two nodes incident to the edge . These are called a pair of stubs.
Drawing is a partial edge drawing (PED) if for all edges , and are given, and at least an edge exists with , where . When , i.e., the lengths of a pair of stubs are the same, the drawing is a symmetric PED (SPED). The smaller parameter is the stubedge ratio. If the stubratios for all edges are the same , the drawing is a symmetric homogeneous PED (SHPED).
Herein, we assume that is given in advance and stubs may have intersections.
3 Related Work
Becker et al. conceived a drawing concept in which only half the links are used to reduce the visual clutter during the development of a tool called SeeNet [2]. Parallel Tagcloud, developed by Collins et al., adopts a method similar to PED [9]. Although Parallel Tagcloud is an extension of Tag Cloud, it can be regarded as a hierarchical layout of directed graphs; thus, it is useful against visual clutter caused by crossing of links. They can avoid drawing intersections by representing links as straight lines without drawing in the middle of the links.
Bruckdorfer et al. formalized the PED in their study [5]; our formalization of PED in Section 2 is a modified version of their formalization. They added continuity of the omitted parts of links as a condition, we have incorporated this into the formalization herein. Moreover, although they focused on a layout without crossing stubs in PED, this study allows stub crossings. Burch et al. applied PED to directed graphs using tapered links [8]. Schmauder et al. applied PED to weighted graphs by representing weights with edge colors [14].
Bruckdorfer et al. performed a comparison between CED^{1}^{1}1They call it the traditional straightline model (TRA). and 1/4SHPED on reading performance of graphs [6]. Although the statistical significance was not shown, from their chart that visualizes the experimental results, in the task of reading graphs (for adjacency check of two nodes or search for adjacent nodes), we can guess that 1/4SHPED is slightly more accurate than CED; however, the response time of the latter is longer. Binucci et al. conducted a more detailed evaluation to reveal that SHPED has high accuracy in reading graphs within SPED [3]. Burch examined the effect of stub orientation and length on graph reading accuracy [7].
Blass et al. avoided using arrows to facilitate grasping highdimensional transitions in the state transition diagram and proposed moving the dashed pattern with animation [4]. Holten et al. compared the recognition accuracy of graphs in various edge drawing methods, such as tapered links and curved links, including animation [11]. They showed that the recognition accuracy of the graph is high by representation using animation. Romat et al. attempted to extend the design space using animation of edge textures [13]. The proposal herein can be considered as an application of animation to graph drawing, especially to drawing edges. However, the purpose is not to express the orientation, but to improve the reading accuracy and efficiency for graphs.
4 Morphing Edge Drawing
Let be a set of times. Then, function , which determines a partial drawing of edge for time , a morphing function. A dynamic drawing of graph with morphing functions is a morphing edge drawing (MED), where is a set of morphing functions.
Then, a function , which determines the partial edge parameters for a time , is a ratio function. The morphing function can be constructed as using the ratio function.
4.1 Symmetric MED
When all for all satisfies () for all , we get SPED at any time. Thus, such a ratio function is a symmetric ratio function; furthermore, if a MED is composed of symmetric ratio functions, it is referred to as a symmetric MED (SMED). As the two values obtained by a symmetric ratio function depend on each other, we can define the function as without ambiguity.
Morphing of edge extending from stubedge ratio to and then shrinking to is expressed by a symmetric ratio function , expressed as Exp. (2), where is the start time of the morphing, is the length of , and is the speed of the tips of the stubs (morphing speed). Here, let the morphing speed be constant. Fig. 1 shows the graph of the function.
(2) 
where is the time when the stubedge ratio becomes , and is the time when the stubedge ratio returns to . Using oneway travel time , and .
If the ratio functions have the same and for all edges, the drawing is a symmetric homogeneous MED (SHMED). Note, this homogeneity does not always mean synchronicity. Drawings by SHMED may not be SHPED at any time.
When , we omit , like symmetric homogeneous MED (SHMED). In the drawing by SHMED, a pair of stubs of edge becomes
at a certain moment. Intuitively, the drawing by
SHMED changes between SHPED and CED. However, a moment when it becomes CED does not always exist.5 Scheduling of Morphing
We have set requirements to design the scheduling of morphing of all edges as follows:
5.0.1 R1: Morphing does not make crossings
To maintain the reading accuracy, visual clutter should be minimized. Therefore, morphing should not result in new crossings among stubs. However, if another edge exists that crosses a stub with a stubedge ratio , then the crossing is inevitable. As mentioned earlier, rearrangements to avoid such crossings are beyond the scope of this paper. The requirement is to avoid crossings in the center area undrawn by SHPED, (we refer to these areas as blank areas).
5.0.2 R2: Shorten morphing time for all edges
The time taken for a viewer to focus on a stub should be minimized before morphing of the stub. We do not know in advance which stubs the viewer will focus on. Therefore, it is necessary to repeat morphing of all edges, and it is necessary to shorten the total morphing time of all edges.
5.1 Morphing Group
First, two noncrossing edges do not generate new crossings of stubs at any timing when morphing, i.e., they can morph simultaneously and independently. However, two edges that do not intersect may not be able to morph independently, depending on the relationship with other edges (see Fig. 2).
A set of edges where the timing of morphing may affect each other is a morphing group. Different morphing groups can be scheduled independently. To determine the morphing groups, another graph is generated from the graph to be drawn. To avoid ambiguity, we will express the newly generated graph and its components as graph, node, and edge. Let each edge be a node. Suppose that there is an edge between nodes (i.e., edges) that intersect each other in a blank area. Nodes (i.e., edges) included in each connected component of the graph generated in this manner constitute a morphing group.
As two edges belonging to different morphing groups do not intersect, it is possible to schedule them independently in units of morphing groups. Hereafter, we describe scheduling of morphing of edges included in a morphing group.
5.2 Sequential Morphing
To prevent new stub crossings from being generated by morphing of two edges intersecting in blank areas, entry into a blank area should be exclusive. That is, the safest scheduling, satisfying requirement R1 (morphing does not result in crossings), is to perform edge morphing sequentially. However, with such simple scheduling, R2 cannot be satisfied.
5.3 Packing Morphing Intervals
Assume there are two intersecting edges and , as shown in Fig. 3. If the scheduling is such that when a stub of edge has been stretched and contracted to the crossing point, a stub of extends to the crossing point, then no intersection will occur. Let the time it takes for the stub of to contract to the crossing point after it starts morphing be and the time it takes for the stub of to start morphing and then extend to the crossing point be . If the stub of edge starts morphing after the stub of starts morphing, no crossing occurs. In addition, when morphing is repeated alternately, will start morphing again next to .
5.4 Parallel Morphing
Even if edges belong to the same morphing group, morphing of two nonintersecting edges may be performed simultaneously. By appropriately morphing parallelly, it is possible to shorten the total morphing time of all edges. For example, as edges and in Fig. 2 are not intersecting, their morphing can be parallelized if we can find adequate timing to avoid crossing with . This can reduce the overall time.
5.5 Algorithm for Finding Morphing Start Time
In scheduling morphing, we decided to determine the start time from longer edges. Assuming that every stub has the same morphing speed, the longer the edge, the longer one cycle of morphing takes. By determining the start time from longer edges, while a long edge is morphing, the morphing of short edges that do not intersect with it can be embedded in the same time range.
Given a morphing group (a set of edges), Algorithm 1 determines the morphing start time for all edges . The algorithm determines the morphing start time in descending order of edge length. It checks the timing of every morphing stub of all edges in that intersect with edge , and allows the morphing start time of edge to be the earliest time that does not result in intersection with the morphing stubs.
The and appearing in the algorithm represents the first and last time of the time range, respectively, when the start of the morphing of edge is prohibited to avoid crossing with edge . They are described as Exp. (3) and Exp. (4).
(3)  
(4) 
where is the time it takes from the start of morphing of the stub of edge to the first passing (passing while stretching) at the crossing point with edge (cf. in Fig. 3), and is the time it takes from the start of morphing to the second passing (passing while shrinking) at the crossing point (cf. in Fig. 3).
Function yields the smallest value not included in the time ranges (intervals) in a given set . If each pair included in the set is regarded as an interval of real numbers, function is defined as Exp. (5). We calculate using Algorithm 2. Note that is a nonnegative real number in Algorithm 2.
(5) 
6 Evaluation Experiment
To investigate the effectiveness of MED, we conducted a comparative experiment with three types of visual representations: CED, 1/4SHPED, and 1/4SHMED.
6.1 Hypothesis
We made the following hypothesis.
 H1

1/4SHMED requires less time to read a graph than 1/4SHPED
 H2

1/4SHMED is more accurate at reading graphs than CED
6.2 Tasks
We designed the following tasks to test the above hypotheses.
 T1

Check if the two highlighted nodes are adjacent (connected by an edge).
 T2

Select all the nodes to which the highlighted node is adjacent.
For T1, as shown in Fig. 5, a graph in which two nodes are highlighted is displayed. Participants respond by pressing “Y” or “N” on the keyboard. When creating sample graphs, the number of crossings of the edges connecting two nodes were set to 8 or 16 when the nodes were adjacent.
For T2, as shown in Fig. 5, a graph in which one node is highlighted is displayed. Node selection is performed using a trackpad. When clicked, the pointed node is selected and turns orange. Participants can also cancel the selection by clicking again. Answers are confirmed by pressing the Enter key. When creating sample graphs, we selected nodes to be highlighted such that the number of adjacent nodes to it were 3, 6, and 9. Furthermore, we set the average number of intersections of the edges of interest to be within 7.9–8.1 and the average of lengths of the edges to be in the range of 3.3–3.7 cm on the screen to ensure that the task difficulty was not excessively low or high. In this experiment, we assumed that the distance between the participant’s eyes and the screen was 40 cm.
(a) CED  (b) 1/4SHPED  (c) 1/4SHMED 
(a) CED  (b) 1/4SHPED  (c) 1/4SHMED 
6.3 Graphs used for the experiment
6.4 Morphing speed
We set the morphing speed of each stub as /s. If morphing is too fast, the human eye cannot track it. Conversely, if it is too slow, reading efficiency is reduced. We derived the speed based on Robinson’s experiment [12] such that it is human eyetrackable while being as fast as possible. However, we set a minimum oneway travel time 300 ms to make capturing morphing stubs easy.
6.5 Experimental settings
We used a MacBook Pro 2017 (screen size 13.3 inches, screen resolution ) for the experiment. We set the display area to so the graph can be viewed without scrolling.
The participants in this experiment were 12 students (4 university students and 8 graduate students).
6.6 Experimental procedure
The following procedure was used to conduct the experiment:
 1

Overall explanation
 2

Visual representation #1
 21

T1 practice (one question)
 22

T1 actual (nine questions)
 23

T2 practice (one question)
 24

T2 actual (nine questions)
 25

Questionnaire for visual representation #1
 3

Visual representation #2 (flow similar to visual representation #1)
 4

Visual representation #3 (flow similar to visual representation #1)
 5

Questionnaire for whole experiment
We varied the order of presenting visual representations from each participant to eliminate the effects of order. Therefore, visual representations #1, #2, and #3 differ depending on the participant. We assigned two participants for each of the six () orders.
6.7 Response time
Fig. 6 shows the distribution (boxplots) of response time (in millisecond) for each task and representation method. In both tasks, the average response time was the lowest for CED and highest for 1/4SHPED. As the 1/4SHMED is located in the middle, an improvement in the reading time for 1/4SHPED can be expected. From the ShapiroWilk test (
), the time taken either task did not follow a normal distribution. Therefore, we performed multiple tests using the Friedman and Holm methods. Tables
2 and 2 show the test results for the response time for T1 and T2, respectively. As shown in Table 2, a significant difference was observed between the representation methods, i.e., 1/4SHMED can shorten the time taken to confirm the adjacency between nodes, compared to 1/4SHPED (H1). In contrast, no significant difference was found between the representation methods with respect to the response time of T2.(a) Task T1 [ms]  (b) Task T2 [ms] 
Comparison  Test result (p value)  Significance level  

CED vs  1/4SHPED  2.035e7  0.0167 
CED vs  1/4SHMED  0.0343  0.0500 
1/4SHPED vs  1/4SHMED  0.0011  0.0250 
Comparison  Test result (p value)  Significance level  

CED vs  1/4SHPED  0.0543  0.0167 
CED vs  1/4SHMED  0.1237  — 
1/4SHPED vs  1/4SHMED  0.8474  — 
6.8 Answer accuracy
Fig. 7(a) shows the number of correct answers and the number of incorrect answers for T1 in a stacked bar chart. The correct answer rate of 1/4SHMED is the highest. However, independence between the representation methods was not recognized from the chisquare test. We defined the score for T2 as the Jaccard coefficient between the set of adjacent nodes and the set of answered nodes, i.e., it is 1 when the two sets completely match, and 0 when there is no common element. Fig. 7(b) shows the distribution of scores according to each representation method for T2 in a boxplot. From the ShapiroWilk test (), T2 did not followed a normal distribution. Therefore, we performed multiple tests using the Friedman and Holm methods. Table 3 shows the test results for the scores T2. As seen above, regarding the accuracy of answers, no significant difference was observed between the representation methods. Therefore, H2 is not supported.
(a) Task T1  (b) Task T2 
Comparison  Test result (p value)  Significance level  

CED vs  1/4SHPED  0.5862  — 
CED vs  1/4SHMED  0.1489  — 
1/4SHPED vs  1/4SHMED  0.07817  0.0167 
6.9 Qualitative Feedback
We asked the participants for opinions on visual representations using questionnaires. The following comments were obtained on 1/4SHMED.

Positive opinions

Morphing made it easy to confirm the exact adjacency.

It can be judged whether two nodes are adjacent by observing the morphing of two stabs works simultaneously.


Negative opinions

It is messy and difficult to see. My eyes are strained.

The stubs change too fast. The time for stubs to connect is too short.

Positive opinions indicate that morphing contributes to reading graphs. In contrast, from the negative opinions, it appears that visual clutter was not always resolved. The following can be considered as the main reasons. The first is that the morphing speed is too fast. In the implementation used for the experiment, to shorten the overall morphing time, the morphing speed was determined based on the tracking speed of human eyes; however, this appears to be too fast. The second is that there were a large number of stubs applying morphing. In the graph used in the experiment, out of the 144 edges, the average number of nonmorphing edges is 24.5. Given that approximately 120 edges repeated morphing, the entire graph is considered to have caused visual clutter.
7 Concluding Remarks
We proposed morphing edge drawing (MED) which is timevarying partial edge drawing (PED) and showed the formalization of MED. We also developed a scheduling scheme for morphing such that dynamic stubs do not cause new crossings. We compared three visual representations, CED, 1/4SHPED, and 1/4SHMED, via a user study, and showed that 1/4SHMED is better than 1/4SHPED in terms of graph reading time. Thus, MED can function as a countermeasure against the time to read a graph by PED. In the future, it is important to investigate eyefriendly morphing that causes less strain and has improved scheduling.
References
 [1] Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). https://doi.org/10.1126/science.286.5439.509
 [2] Becker, R.A., Eick, S.G., Wilks, A.R.: Visualizing network data. IEEE Transactions on Visualization and Computer Graphics 1(1), 16–28 (March 1995). https://doi.org/10.1109/2945.468391
 [3] Binucci, C., Liotta, G., Montecchiani, F., Tappini, A.: Partial edge drawing: Homogeneity is more important than crossings and ink. In: 2016 7th International Conference on Information, Intelligence, Systems Applications (IISA). pp. 1–6 (July 2016). https://doi.org/10.1109/IISA.2016.7785427
 [4] Blaas, J., Botha, C., Grundy, E., Jones, M., Laramee, R., Post, F.: Smooth graphs for visual exploration of higherorder state transitions. IEEE Transactions on Visualization and Computer Graphics 15(6), 969–976 (Nov 2009). https://doi.org/10.1109/TVCG.2009.181
 [5] Bruckdorfer, T., Kaufmann, M.: Mad at edge crossings? break the edges! In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) Fun with Algorithms. pp. 40–50. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
 [6] Bruckdorfer, T., Kaufmann, M., Leibßle, S.: PED user study. In: Di Giacomo, E., Lubiw, A. (eds.) Graph Drawing and Network Visualization. pp. 551–553. Springer International Publishing, Cham (2015)
 [7] Burch, M.: A user study on judging the target node in partial link drawings. In: 2017 21st International Conference Information Visualisation (iV). pp. 199–204 (July 2017). https://doi.org/10.1109/iV.2017.43
 [8] Burch, M., Vehlow, C., Konevtsova, N., Weiskopf, D.: Evaluating partially drawn links for directed graph edges. In: van Kreveld, M., Speckmann, B. (eds.) Graph Drawing. pp. 226–237. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
 [9] Collins, C., Viégas, F.B., Wattenberg, M.: Parallel tag clouds to explore and analyze faceted text corpora. In: 2009 IEEE Symposium on Visual Analytics Science and Technology. pp. 91–98 (Oct 2009). https://doi.org/10.1109/VAST.2009.5333443
 [10] Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by forcedirected placement. Software: Practice and Experience 21(11), 1129–1164 (1991). https://doi.org/10.1002/spe.4380211102
 [11] Holten, D., Isenberg, P., van Wijk, J.J., Fekete, J.: An extended evaluation of the readability of tapered, animated, and textured directededge representations in nodelink graphs. In: 2011 IEEE Pacific Visualization Symposium. pp. 195–202 (March 2011). https://doi.org/10.1109/PACIFICVIS.2011.5742390
 [12] Robinson, D.A.: The mechanics of human smooth pursuit eye movement. The Journal of Physiology 180(3), 569–591 (1965). https://doi.org/10.1113/jphysiol.1965.sp007718
 [13] Romat, H., Appert, C., Bach, B., HenryRiche, N., Pietriga, E.: Animated edge textures in nodelink diagrams: A design space and initial evaluation. In: Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. pp. 187:1–187:13. CHI ’18, ACM, New York, NY, USA (2018). https://doi.org/10.1145/3173574.3173761, http://doi.acm.org/10.1145/3173574.3173761
 [14] Schmauder, H., Burch, M., Weiskopf, D.: Visualizing dynamic weighted digraphs with partial links. In: Proceedings of 6th International Conference on Information Visualization Theory and Applications (IVAPP). pp. 123–130 (2015)
Comments
There are no comments yet.