Multi-level graph layout on the GPU

This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.     

A stable graph layout algorithm for processes

Process mining enables organizations to analyze data about their (business) processes. Visualization is key to gaining insight into these processes and the associated data. Process visualization requires a high‐quality graph layout that intuitively represents the semantics of the process. Process analysis additionally requires interactive filtering to explore the process data and process graph. The ideal process visualization therefore provides a high‐quality, intuitive layout and preserves the mental map of the user during the visual exploration. The current industry standard used for process visualization does not satisfy either of these requirements. In this paper, we propose a novel layout algorithm for processes based on the Sugiyama framework. Our approach consists of novel ranking and order constraint algorithms and a novel crossing minimization algorithm. These algorithms make use of the process data to compute stable, high‐quality layouts. In addition, we use phased animation to further improve mental map preservation. Quantitative and qualitative evaluations show that our approach computes layouts of higher quality and preserves the mental map better than the industry standard. Additionally, our approach is substantially faster, especially for graphs with more than 250 edges.     

Techniques for Edge Stratification of Complex Graph Drawings

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.     

Perfect Matching Quad Layouts for Manifold Meshes

This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.     

Customizing a Fisheye View Algorithm to Preserve the Mental Map

Frequently, large knowledge bases are represented by graphs. Many visualization tools allow users or other applications to interact with and adjust the layouts of these graphs. One layout adjustment problem is that of showing more detail without eliding parts of the graph. Approaches based on a fisheye lens paradigm seem well suited to this task. However, many of these techniques are non-trivial to implement and their distortion techniques often cannot be altered to suit different graph layouts. When distorting a graph layout, it is often desirable to preserve various properties of the original graph in an adjusted view. Pertinent properties may include straightness of lines, graph topology, orthogonalities and proximities. However, it is normally not possible to preserve all of the original properties of the graph layout. The type of layout and its application should be considered when deciding which properties to preserve or distort. This paper describes a fisheye view algorithm which can be customized to suit various different graph layouts. In contrast to other methods, the user can select which properties of the original graph layout to preserve in an adjusted view. The technique is demonstrated through its application to visualizing structures in large software systems.     

一种用于Marching-Graph图形绘制的快速收敛布局算法

Marching-Graph是一种将图形隐喻技术和空间隐喻技术集成为一体的新的可视化方法.它为用户提供了高度可交互性地图,使用户可访问那些具有地理属性的信息的逻辑结构.它通过有效的人图交互和跨空间浏览为用户提供了一种可视分析和挖掘未知信息的机制,而不是将已知的信息呈现在地图上.然而,传统的力导向布局算法在达到力量均衡配置方面非常慢.为使一个图形布局收敛,它们通常需花费几十秒的时间.因此。当用户快速行进于地理区间时,那些力导向布局算法就不能满足快速绘制一系列图形的要求.提出了一种快速收敛布局方法,当用户在Marching-Graph中通过力导向布局逐步探究一系列图形时,它可以加速交互时间.通过结合辐射树绘图技术和力导向图形绘制方法来取得能量最小化的快速收敛.     

FMR:基于FR的快速多层次算法

图可视化技术是可视化研究的重要内容,近年来大图的绘制问题一直是图可视化 技术的焦点。为此,提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为 算法的框架,以 FR 力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进 行优化。另外,还使用了约束规范化和能量模型 2 种加速方法。实验表明,该算法具有高效的 性能和良好的布局效果。其效率非常高,在单核 CPU 下,可以在大约 5 s 内很好地绘制出 10 000 个顶点的图。并与几种经典的算法进行了比较,也证明了该算法的有效性和实用性。此外,该 算法易于实现,可被轻易推广到其他布局算法上,以加速其运算。     

A regularized graph layout framework for dynamic network visualization

Many real-world networks, including social and information networks, are dynamic structures that evolve over time. Such dynamic networks are typically visualized using a sequence of static graph layouts. In addition to providing a visual representation of the network structure at each time step, the sequence should preserve the mental map between layouts of consecutive time steps to allow a human to interpret the temporal evolution of the network. In this paper, we propose a framework for dynamic network visualization in the on-line setting where only present and past graph snapshots are available to create the present layout. The proposed framework creates regularized graph layouts by augmenting the cost function of a static graph layout algorithm with a grouping penalty, which discourages nodes from deviating too far from other nodes belonging to the same group, and a temporal penalty, which discourages large node movements between consecutive time steps. The penalties increase the stability of the layout sequence, thus preserving the mental map. We introduce two dynamic layout algorithms within the proposed framework, namely dynamic multidimensional scaling and dynamic graph Laplacian layout. We apply these algorithms on several data sets to illustrate the importance of both grouping and temporal regularization for producing interpretable visualizations of dynamic networks.     

Uncluttering Graph Layouts Using Anisotropic Diffusion and Mass Transport

Many graph layouts include very dense areas, making the layout difficult to understand. In this paper, we propose a technique for modifying an existing layout in order to reduce the clutter in dense areas. A physically inspired evolution process based on a modified heat equation is used to create an improved layout density image, making better use of available screen space. Using results from optimal mass transport problems, a warp to the improved density image is computed. The graph nodes are displaced according to the warp. The warp maintains the overall structure of the graph, thus limiting disturbances to the mental map, while reducing the clutter in dense areas of the layout. The complexity of the algorithm depends mainly on the resolution of the image visualizing the graph and is linear in the size of the graph. This allows scaling the computation according to required running times. It is demonstrated how the algorithm can be significantly accelerated using a graphics processing unit (GPU), resulting in the ability to handle large graphs in a matter of seconds. Results on several layout algorithms and applications are demonstrated.