Are Crossings Important for Drawing Large Graphs? - Graph Drawing - page 238

3.1 Procedure: Experiment 1

Real-world graphs are typically large and non-planar. In drawingsofsuch graphs there
could be many edge crossings, which likely makes the drawingsdifficult to understand.
To evaluate the impact of the number of crossings for different sizes and densities of
graphs, while keeping the experiment to a reasonable length and complexity, we want
to choose the graphs so that the average completion time is below 120 seconds and the
average accuracy for a single task is higher than 50%.
To determine reasonable upper limits for the main experiment, we generated different
graphs with 100-150 vertices, in increments of 10, and densities ranging from 1 . 5 to
3 . 5, in increments of 1.Foreverygraph, we used the layout with the smallest number
of crossings and for each of these layouts the participants performed the fourtasks
described above. The resulting completion time ranges from 63 seconds for a 100-
vertex graph to 184 seconds for a 150-vertex graph. The accuracy (the number of correct
answers divided by the total number of questions) ranges from 85% for 100-vertex
graphs with 1 . 5 density to 39% for 150-vertex graphs with 3 . 5 density. Based on these
results, we choose 120 vertices as the maximumnumber of vertices and 2 . 5 as the
maximum density valueforour main experiment.

3.2 Procedure: Experiment 2

An experimental system was implemented to present the 64 (2 sizes × 2 number of

crossings 4 tasks ) stimuli and questions for this within-

subjects experiment, and to collect the participant answers and response times.
Before the controlled experiment, the participants were briefed aboutthepurpose
of the study. Although all participants were familiar with graphs, we explained all the
required definitions (e.g., graphs, edges, paths). The participants then answered 8 train-
ing questions (two for each of the tasks) as quickly and as accurately as possible. The
participants were encouraged to ask questions during this stage and we did not record
time and accuracy for the training questions.
The main experiment consisted of the 64 tasks, presented in a reduced Latin square
to counterbalance learning and order effects (to prevent participants from extrapolating
new judgements from previous ones). The participants were able to zoom and pan the
diagram on the screen (if needed) and were required to select one of the provided mul-
tiple choices. We recorded time and accuracy for each task. After every 12 questions,
there was a break and the participants could continue when they were ready.

× 2 densities × 2 datasets ×

Hypotheses. Based on prior work and results from our preliminary experiment, we
hypothesize that:

H1 Increasing the number of crossingsnegatively impacts accuracy and performance
time and that impact is significant for small graphs but not significant for large
graphs.
H2 The negative impact of increasing the number of crossings on performance is sig-
nificant for both small sparse and small dense graphs.
H3 The negative impact of increasing the number of crossings on performance is not
significant for both large sparse and largedensegraphs.