Evaluating esthetics for user-sketched layouts of clustered graphs with known clustering information

Abstract

This paper aims to empirically analyze the esthetics for user-sketched layouts of clustered graphs with known clustering information. In our experiments, given not only the adjacency list of a clustered graph but also its predefined clustering information, each participant was asked to manually sketch clustered graphs “nicely” from scratch on a tablet system using a stylus. Different from previous works, the main concern in this paper is on which graph drawing esthetics people favor when sketching their own drawings of clustered graphs with known clustering information. Another concern of this paper is on the esthetics of clustered graph layouts employed by participants which include not only characteristics and structures of the final graph layouts but also the behavior of user's sketching process (including layout creation and adjustment). By observing all layouts and drawing processes, the drawing strategies which participants applied and the drawing esthetics are analyzed. Results show that most participants were unsurprisingly able to draw graphs with clear presence of bridge edges and clustering cohesiveness; more importantly, to distinguish clusters within the restricted-size tablet screen during the drawing process, some of the participants were still able to make each cluster with fewer edge crossings, more symmetries, and more alignment of grid in a smaller drawing area where the cluster spreads. Our results support that to alleviate user's complex drawing tasks, aside from the grid-based editing function suggested by the previous work, graph drawing systems should also provide the clustering information if the structure of the graph to be drawn is known.

Introduction

For about the past 30 years, most of the graph drawing algorithms have been developed to automatically produce graph layouts in an esthetically pleasing way, i.e., to optimize the predefined esthetic criteria as much as possible. Esthetic criteria in graph drawing indicate graphic structures and properties of graph layouts, such as minimizing number of edge crossings or bends, maximizing number of symmetries, minimizing the drawing area, keeping uniform edge lengths, among others. However, it is generally NP-hard to simultaneously optimize those criteria, in many cases, e.g., force-directed graph drawing algorithm for general graphs [8], [4], [11], [14], [10] and clustered graphs [9], [6], [5]. These problems have been studied extensively in the literature [19], [9]. In those automatic graph drawing algorithms, the esthetic criteria to be optimized are typically determined from the algorithm designers' points of view, not how the user lays out graphs.

In recent years, a great deal of empirical research has focused on whether esthetics of the drawings generated by automatic graph drawing algorithms can really help users’ understanding, e.g., minimizing number of edge crossings, minimizing number of edge bends, and maximizing the included angles [20], [16], [27], [13]. However, these works mostly addressed the ability of users in reading and interpreting an already presented graph layout, produced by an automatic graph drawing algorithm. Hence, another line of the empirical research is to investigate the graph layouts sketched manually by users, e.g., the work in [17] concluded that edge crossings and grid aligning are considered as the most important factors among user-sketched graph drawing esthetics.

Clustered graphs could provide users more insights into organization of complicated graphs. Hence, it has been of much interest to investigate how to draw clustered graphs “nicely” [2]. This paper extends the works in [17], [1], [21] to further investigate the esthetics specifically for user-sketched layouts of clustered graphs with known clustering information. Note that the case without any clustering information has been studied implicitly in [21], so this work further realizes user-sketched clustered graph drawings when their clustering information is provided initially. To achieve this goal, during the experiments, aside from the adjacency list of the experimental clustered graph, we additionally provide the participants the clustering information of the clustered graph, i.e., the information on which cluster each vertex belongs to is known. The participants were asked to sketch the clustered graph as “nicely” as possible based on the given adjacency list and the clustering information.

Note that graph clustering problems (i.e., determining how to classify vertices into clusters) with and without known number of clusters are different, and both problems have been widely studied. Generally, the graph clustering problem with known number of clusters is regarded as being easier than the other problem. This inspires us to investigate whether providing more information on graph clustering can help users sketch clustered graphs. However, only providing number of clusters is still too difficult for users to sketch graphs from scratch. Hence, this work provides the information on clustering partition of vertices, and intends to realize whether users are able to sketch clustered graphs “nicely” (not only to classify vertices in visualization) with this information.

The experimental design of this work is based on the work in [21], which compared differences between the layouts for two graphs produced by all participants; and compared the effects of different participant backgrounds. Hence, after obtaining those user-sketched clustered graph layouts and observing their drawing processes, we intend to explore importance of particular esthetic criteria which might reveal visual information that has not previously been defined yet. That is, characteristics of the sketched clustered graph drawings and importance of representing cluster structures might be found to provide more direct insight into how users organize vertices in representing clustered graph drawings. Additionally, qualitative rating task was designed to visually assess goodness of a clustering structure in respect to some esthetic criteria specifically for clustered graphs. For each resultant drawing, we rate the quality from one to five on Likert scale.

The rest of the paper is organized as follows. In Section 2, the main related works are surveyed, and then, the two main previous works related to this work are presented in more detail. Section 3 gives the details of our experiments, including equipment, task, participant, procedure, and the overall experimental process. Then, experimental results for graph layouts and drawing process are analyzed in Sections 4 and 5, respectively. Section 6 applies a ranking task by the experimenter to validate the experimental results and analyzes the participants' background. Finally, conclusions and future works are given in Section 7.