Online Dynamic Graph Drawing

This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and, thus, the user’s mental map while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are

provided. Index Terms—Graph layout, GPU. Ç 1INTRODUCTION G RAPH drawing addresses the problem of constructing geometric representations of graphs [1]. It has applica- tions in a variety of areas, including software engineering, software visualization, databases, information systems, decision support systems, biology, chemistry, and social networks. Many applications require the ability of dynamic graph drawing, that is, the ability to modify the graph [1], [2], [3], as illustrated in Fig. 1. Sample applications include financial analysis, network visualization, security, social networks, and software visualization. The challenge in dynamic graph drawingisto computeanew layoutthatisboth aesthetically pleasing as it stands and fits well into the sequence of drawings of the evolving graph. Thelatter criterion has been termed preserving the mental map [4] or dynamic stability [2]. Most existing algorithms address the problem of offline dynamicgraphdrawing,wheretheentiresequenceofgraphs to be drawn is known in advance [3], [5], [6]. This gives the layout algorithm information about future changes in the graph, which allows it to optimize the layouts generated across the entire sequence. For instance, the algorithm can leaveplaceinordertoaccommodateanodethatappearslater inthesequence.Incontrast,verylittleresearchhasaddressed the problem of online dynamic graph drawing, where the graphsequencetobelaidoutisnotknowninadvance[7],[8]. This paper proposes an online algorithm for dynamic layout of graphs. It attempts to maintain the user’s mental map while computing fast layouts that take the global graph structure into account. The algorithm, which is based on force-directed layout techniques, controls the displacement of nodes according to the structure and changes performed on the graph. By taking special care in order to represent the graph in a GPU-efficient manner, the algorithm is able to make use of the GPU to significantly accelerate the layout. This paper makes the following contributions: First, a novel, efficient algorithm for online dynamic graph drawing is presented. It spends most of the execution time on the parts of the graph being modified. Second, it is shown how the heaviest part of the algorithm, performing force-directed layout, can be implemented in a manner suitable for executionontheGPU.Thisallowsustosignificantlyshorten the layout time. For example, the incremental drawing of a graph of 32,000 nodes takes 0.704 second per layout. Finally, two information visualization applications of the algorithm are presented. The first is the visualization of the evolution over time of discussion threads in Internet sites. In this application, illustrated in Fig. 1, nodes represent users, and edges represent messages sent between users in discussion forums. The second application is the visualization of the growth of a social network,...

Website: www.cse.ohio-state.edu | Filesize: -
No of Page(s): 14
Download Online Dynamic Graph Drawing - Computer Science & Engineering ....pdf