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.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

Parametric graph drawing

A diagram is a drawing on the plane that represents a graph like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams     

Interactive 3D Force‐Directed Edge Bundling

Interactive analysis of 3D relational data is challenging. A common way of representing such data are node‐link diagrams as they support analysts in achieving a mental model of the data. However, naïve 3D depictions of complex graphs tend to be visually cluttered, even more than in a 2D layout. This makes graph exploration and data analysis less efficient. This problem can be addressed by edge bundling. We introduce a 3D cluster‐based edge bundling algorithm that is inspired by the force‐directed edge bundling (FDEB) algorithm [ HvW09b ] and fulfills the requirements to be embedded in an interactive framework for spatial data analysis. It is parallelized and scales with the size of the graph regarding the runtime. Furthermore, it maintains the edge's model and thus supports rendering the graph in different structural styles. We demonstrate this with a graph originating from a simulation of the function of a macaque brain.     

On simultaneous straight-line grid embedding of a planar graph and its dual

Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n−2)×(2n−2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n−1)×n.     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

A general method for drawing area-proportional Euler diagrams

Area-proportional Euler diagrams have many applications, for example they are often used for visualizing data in medical and biological domains. There have been a number of recent research efforts to automatically draw Euler diagrams when the areas of the regions are not considered, leading to a range of different drawing techniques. By contrast, substantially less progress has been made on the problem of automatically drawing area-proportional Euler diagrams, although some partial results have been derived. In this paper, we considerably advance the state-of-the-art in area-proportional Euler diagram drawing by presenting the first method that is capable of generating such a diagram given any area-proportional specification. Moreover, our drawing method is sufficiently flexible that it allows one to specify which of the typically enforced well-formedness conditions should be possessed by the to-be-drawn Euler diagram.     

UML类图层次化自动布图算法

UML类图能够有效地帮助软件工程师理解大规模的软件系统,而优化图元的空间布局可以增强类图的可读性和可理解性.由于类图中继承关系具有明显的层次特性,因此类图自动布局大多采用层次化的布图算法.此外,类图布局需要考虑相关的领域知识以及绘制准则,因而通用嵌套有向图层次化布局算法不能直接用于类图的绘制,它们必须加以扩展.但是,已有的类图层次化方法并没有考虑类图中图元的嵌套关系,这将导致自动布局方法不能处理类图中包与类、接口之间的包含关系.在考虑图绘制美学、UML类图绘制以及软件可视化等相关知识的基础上,选取了一组布     

A layout algorithm for undirected compound graphs

We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions.     

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.     

Multidimensional Projections for Visual Analysis of Social Networks

Visual analysis of social networks is usually based on graph drawing algorithms and tools.However,social networks are a special kind of graph in the sense that interpretation of displayed relationships is heavily dependent on context.Context,in its turn,is given by attributes associated with graph elements,such as individual nodes,edges,and groups of edges,as well as by the nature of the connections between individuals.In most systems,attributes of individuals and communities are not taken into consideration during graph layout,except to derive weights for force-based placement strategies.This paper proposes a set of novel tools for displaying and exploring social networks based on attribute and connectivity mappings.These properties are employed to layout nodes on the plane via multidimensional projection techniques.For the attribute mapping,we show that node proximity in the layout corresponds to similarity in attribute,leading to easiness in locating similar groups of nodes.The projection based on connectivity yields an initial placement that forgoes force-based or graph analysis algorithm,reaching a meaningful layout in one pass.When a force algorithm is then applied to this initial mapping,the final layout presents better properties than conventional force-based approaches.Numerical evaluations show a number of advantages of pre-mapping points via projections.User evaluation demonstrates that these tools promote ease of manipulation as well as fast identification of concepts and associations which cannot be easily expressed by conventional graph visualization alone.In order to allow better space usage for complex networks,a graph mapping on the surface of a sphere is also implemented.     

一个任意图的输出和编辑系统

本文给出了一个对任意图的输出算法，这个算法同其它的同类算法相比，具有更小的时间复杂性，并且由于此算法的参数是可控制的，所以对图的输出也是可控制的．另外，本文描述了一个图的显示和编辑系统ＧＬＥＡＭ，这个系统是基于所给出的新算法的，并且在本系统中使用了约束技术，使图的输出更美观、合理．ＧＬＥＡＭ是一个通用且可以扩充的系统，用户只要加入相应的具体领域知识，就可把其变为一个专用的系统.     

Event-driven grammars: relating abstract and concrete levels of visual languages

In this work we introduce event-driven grammars, a kind of graph grammars that are especially suited for visual modelling environments generated by meta-modelling. Rules in these grammars may be triggered by user actions (such as creating, editing or connecting elements) and in their turn may trigger other user-interface events. Their combination with triple graph transformation systems allows constructing and checking the consistency of the abstract syntax graph while the user is building the concrete syntax model, as well as managing the layout of the concrete syntax representation. As an example of these concepts, we show the definition of a modelling environment for UML sequence diagrams. A discussion is also presented of methodological aspects for the generation of environments for visual languages with multiple views, its connection with triple graph grammars, the formalization of the latter in the double pushout approach and its extension with an inheritance concept. This is a revised and extended version of a paper presented at the ICGT’04 conference, see [21].     

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

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.     

Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference

In this paper we will present a graph-transformation based method for the verification of heterogeneous first order logic (FOL) and Euler/Venn proofs. In previous work, it has been shown that a special collection of directed acyclic graphs (DAGs) can be used interchangeably with Euler/Venn diagrams in reasoning processes. Thus, proofs which include Euler/Venn diagrams can be thought of as proofs with DAGs where steps involving only Euler/Venn diagrams can be treated as particular DAG transformations. Here we will show how the characterization of these manipulations can be used to verify Euler/Venn proofs. Also, a method for verifying the use of heterogeneous Euler/Venn and FOL reasoning rules will be presented that is also based upon DAG transformations .     

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.     

Minimising the Number of Bends and Volume in 3-Dimensional Orthogonal Graph Drawings with a Diagonal Vertex Layout

A 3-dimensional orthogonal drawing of a graph with maximum degree at most 6, positions the vertices at grid-points in the 3-dimensional orthogonal grid, and routes edges along grid-lines such that edge routes only intersect at common end-vertices. Minimising the number of bends and the volume of 3-dimensional orthogonal drawings are established criteria for measuring the aesthetic quality of a given drawing. In this paper we present two algorithms for producing 3-dimensional orthogonal graph drawings with the vertices positioned along the main diagonal of a cube, so-called diagonal drawings. This vertex-layout strategy was introduced in the 3-BENDS algorithm of Eades et al. [Discrete Applied Math. 103:55–87, 2000]. We show that minimising the number of bends in a diagonal drawing of a given graph is NP-hard. Our first algorithm minimises the total number of bends for a fixed ordering of the vertices along the diagonal in linear time. Using two heuristics for determining this vertex-ordering we obtain upper bounds on the number of bends. Our second algorithm, which is a variation of the above-mentioned 3-BENDS algorithm, produces 3-bend drawings with n³+o(n³) volume, which is the best known upper bound for the volume of 3-dimensional orthogonal graph drawings with at most three bends per edge.     

Simplicity in Eulerian circuits: Uniqueness and safety

An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph G has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte (1941–1951) [15], [16] (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of G), both of which thus rely on overly complex notions for the simpler uniqueness problem.In this paper we give a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. This is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of G. As a by-product, we can also compute in linear-time all maximal safe walks appearing in all Eulerian circuits, for which Nagarajan and Pop proposed in 2009 [12] a polynomial-time algorithm based on Pevzner characterization.