On the Parameterized Complexity of Layered Graph Drawing

We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for fixed h). This algorithm is extended to solve related problems, including allowing at most k crossings, or removing at most r edges to leave a crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed parameter then these problems are NP-complete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case either the total span or the maximum span of edges can be minimized. In contrast to the Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers. Research initiated at the International Workshop on Fixed Parameter Tractability in Graph Drawing, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 9–16, 2001, organized by S. Whitesides. Research of Canada-based authors is supported by NSERC; research of Quebec-based authors is also supported by a grant from FCAR. Research of D.R. Wood completed while visiting McGill University. Research of G. Liotta supported by CNR and MURST.     

Drawing graphs with right angle crossings

Cognitive experiments show that humans can read graph drawings in which all edge crossings are at right angles equally well as they can read planar drawings; they also show that the readability of a drawing is heavily affected by the number of bends along the edges. A graph visualization whose edges can only cross perpendicularly is called a RAC (Right Angle Crossing) drawing. This paper initiates the study of combinatorial and algorithmic questions related to the problem of computing RAC drawings with few bends per edge. Namely, we study the interplay between number of bends per edge and total number of edges in RAC drawings. We establish upper and lower bounds on these quantities by considering two classical graph drawing scenarios: The one where the algorithm can choose the combinatorial embedding of the input graph and the one where this embedding is fixed.     

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.     

A new force-directed graph drawing method based on edge–edge repulsion

The conventional force-directed methods for drawing undirected graphs are based on either vertex–vertex repulsion or vertex–edge repulsion. In this paper, we propose a new force-directed method based on edge–edge repulsion to draw graphs. In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge–edge and vertex–vertex repulsive forces in drawing a graph.     

Larger crossing angles make graphs easier to read

Objective: Aesthetics are important in algorithm design and graph evaluation. This paper presents two user studies that were conducted to investigate the impact of crossing angles on human graph comprehension.Method and results: These two studies together demonstrate our newly proposed two-step approach for testing graph aesthetics. The first study is a controlled experiment with purposely-generated graphs. Twenty-two subjects participated in the study and were asked to determine the length of a path which was crossed by a set of parallel edges at different angles. The result of an analysis of variance showed that larger crossing angles induced better task performance. The second study was a non-controlled experiment with general real world graphs. Thirty-seven subjects participated in the study and were asked to find the shortest path of two pre-selected nodes in a set of graph drawings. The results of simple regression tests confirmed the negative effect of small crossing angles. This study also showed that among our four proposed candidates, the minimum crossing angle on the path was the best measure for the aesthetic when path finding is important.Conclusion: Larger crossing angles make graphs easier to read.Implications: In situations where crossings cannot be completely removed (for example, graphs are non-planar, or a drawing convention is applied), or where effort needed to remove all crossings cannot be justified, the crossing angle should be maximized to reduce the negative impact of crossings to the minimum.     

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.     

A neural-network algorithm for a graph layout problem

We present a neural-network algorithm for minimizing edge crossings in drawings of nonplanar graphs. This is an important subproblem encountered in graph layout. The algorithm finds either the minimum number of crossings or an approximation thereof and also provides a linear embedding realizing the number of crossings found. The parallel time complexity of the algorithm is O(1) for a neural network with n(2) processing elements, where n is the number of vertices of the graph. We present results from testing a sequential simulator of the algorithm on a set of nonplanar graphs and compare its performance with the heuristic of Nicholson.     

ImPrEd: An Improved Force‐Directed Algorithm that Prevents Nodes from Crossing Edges

PrEd [ [Ber00] ] is a force‐directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler‐like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly‐restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEdproves to be consistently faster than PrEd.     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

2-Layer Right Angle Crossing Drawings

A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is $\mathcal{NP}$ -complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings.     

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

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

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.     

GO: A cluster algorithm for graph visualization

As we are in the big data age, graph data such as user networks in Facebook and Flickr becomes large. How to reduce the visual complexity of a graph layout is a challenging problem. Clustering graphs is regarded as one of effective ways to address this problem. Most of current graph visualization systems, however, directly use existing clustering algorithms that are not originally developed for the visualization purpose. For graph visualization, a clustering algorithm should meet specific requirements such as the sufficient size of clusters, and automatic determination of the number of clusters. After identifying the requirements of clustering graphs for visualization, in this paper we present a new clustering algorithm that is particularly designed for visualization so as to reduce the visual complexity of a layout, together with a strategy for improving the scalability of our algorithm. Experiments have demonstrated that our proposed algorithm is capable of detecting clusters in a way that is required in graph visualization.     

Efficient Orthogonal Drawings of High Degree Graphs

Most of the work that appears in the two-dimensional orthogonal graph drawing literature deals with graphs whose maximum degree is four. In this paper we present an algorithm for orthogonal drawings of simple graphs with degree higher than four. Vertices are represented by rectangular boxes of perimeter less than twice the degree of the vertex. Our algorithm is based on creating groups / pairs of vertices of the graph. The orthogonal drawings produced by our algorithm have area at most (m-1) ( m / 2 +2) . Two important properties of our algorithm are that the drawings exhibit a small total number of bends (less than m ), and that there is at most one bend per edge. Received January 15, 1997; revised February 1, 1998.     

A technique for drawing directed graphs

A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast     

用多层次聚类法完成的大规模关系图的可视化

提出了一种新的大规模图形可视化技术.它可显示含有几万个接点和边的大规模关系图.为了完成对图形的抽象化。一个多层次的聚类图形从原始的大规模关系图中抽取了出来.这种抽取是建立在大规模关系图的内在结构基础上来完成的.一种递规封入式的几何划分算法被应用来完成对几何空间的优化,在具体的制图技术上,使用了一种用力导向布局算法和环形制图法相结合的新方法,从而完成了对显示空间的优化和美擘上的优化.同时也讨论了相关的人机交互技术,所采用的人机交互算法不仅能让使用者从上到下层次式地浏览整个聚类图形。同时也能提供多层次聚类图形的并行浏览.动画技术也同时被运用,以保护使用者的精神图不被打乱.     

The Perception of Graph Properties in Graph Layouts

When looking at drawings of graphs, questions about graph density, community structures, local clustering and other graph properties may be of critical importance for analysis. While graph layout algorithms have focused on minimizing edge crossing, symmetry, and other such layout properties, there is not much known about how these algorithms relate to a user's ability to perceive graph properties for a given graph layout. In this study, we apply previously established methodologies for perceptual analysis to identify which graph drawing layout will help the user best perceive a particular graph property. We conduct a large scale (n = 588) crowdsourced experiment to investigate whether the perception of two graph properties (graph density and average local clustering coefficient) can be modeled using Weber's law. We study three graph layout algorithms from three representative classes (Force Directed ‐ FD, Circular, and Multi‐Dimensional Scaling ‐ MDS), and the results of this experiment establish the precision of judgment for these graph layouts and properties. Our findings demonstrate that the perception of graph density can be modeled with Weber's law. Furthermore, the perception of the average clustering coefficient can be modeled as an inverse of Weber's law, and the MDS layout showed a significantly different precision of judgment than the FD layout.     

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.     

Metrics for Graph Drawing Aesthetics

Graph layout algorithms typically conform to one or more aesthetic criteria (e.g. minimizing the number of bends, maximizing orthogonality). Determining the extent to which a graph drawing conforms to an aesthetic criterion tends to be done informally, and varies between different algorithms. This paper presents formal metrics for measuring the aesthetic presence in a graph drawing for seven common aesthetic criteria, applicable to any graph drawing of any size. The metrics are useful for determining the aesthetic quality of a given graph drawing, or for defining a cost function for genetic algorithms or simulated annealing programs. The metrics are continuous, so that aesthetic quality is not stated as a binary conformance decision (i.e. the drawing either conforms to the aesthetic or not), but can be stated as the extent of aesthetic conformance using a number between 0 and 1. The paper presents the seven metric formulae. The application of these metrics is demonstrated through the aesthetic analysis of example graph drawings produced by common layout algorithms.     

Game level layout from design specification

The design of video game environments, or levels, aims to control gameplay by steering the player through a sequence of designer‐controlled steps, while simultaneously providing a visually engaging experience. Traditionally these levels are painstakingly designed by hand, often from pre‐existing building blocks, or space templates. In this paper, we propose an algorithmic approach for automatically laying out game levels from user‐specified blocks. Our method allows designers to retain control of the gameplay flow via user‐specified level connectivity graphs, while relieving them from the tedious task of manually assembling the building blocks into a valid, plausible layout. Our method produces sequences of diverse layouts for the same input connectivity, allowing for repeated replay of a given level within a visually different, new environment. We support complex graph connectivities and various building block shapes, and are able to compute complex layouts in seconds. The two key components of our algorithm are the use of configuration spaces defining feasible relative positions of building blocks within a layout and a graph‐decomposition based layout strategy that leverages graph connectivity to speed up convergence and avoid local minima. Together these two tools quickly steer the solution toward feasible layouts. We demonstrate our method on a variety of real‐life inputs, and generate appealing layouts conforming to user specifications.