Graph Drawing

It is proposed that research into human perception can be applied in designing ways to represent structured information. This idea is illustrated with four case studies. (1) How can we design a graph so that paths can be discerned? Recent results in the perception of contours can be applied to make paths easier to perceive in directed graphs. (2) Should we be displaying graphs in 3D or 2D space? Research suggests that larger graphs can be understood if stereo and motion parallax depth cues are available. (3) How can heterogeneous information structures be best represented? Experiments show using structured 3D shape primitives make diagrams that are easier to discover and remember. (4) How can causal relationships be displayed? Michotte’s work on the perception of causality suggests that causal relationships can be represented using simple animations. The general point of these examples is that data visualization can become a science based on the mapping of data structures to visual representations. Scientific methods can be applied both in the development of theory and testing the value of different representations.

The merit of automatic graph layout algorithms is typically judged on their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Experiments investigating the worth of such algorithms from the point of view of human usability can take a number of different forms, depending on whether the graph has meaning in the real world, the nature of the usability measurement, and the effect being investigated (algorithms or aesthetics). Previous studies have investigated performance on abstract graphs with respect to both aesthetics and algorithms, finding support for reducing the number of crossings and bends, and increasing the display of symmetry.This paper reports on preference experiments assessing the effect of individual aesthetics in the application domain of UML diagrams, resulting in a priority listing of aesthetics for this domain. The results reveal a difference in aesthetic priority from those of previous domain-independent experiments.

The need for a similarity measure for comparing two drawings of graphs arises in problems such as interactive graph drawing and the indexing or browsing of large sets of graphs. This paper builds on our previous work [3] by defining some additional similarity measures, refining some existing ones, and presenting the results of a user study designed to evaluate the suitability of the measures.

Partitioning is often used to support better graph drawing; in this paper, we describe an interactive system in which graph drawing is used to support better partitioning. In our system the user is presented with a drawing of a current network partitioning, and is responsible for choosing appropriate optimization procedures and for focusing their application on portions of the network. Our pilot experiments show that our network drawings succeed in conveying some of the information needed by the human operator to steer the computation effectively, and suggest that interactive, human-guided search may be a useful alternative to fully automatic methods for network and graph partitioning.

We present an experimental study in which we compare the state-of-the-art methods for compacting orthogonal graph layouts. Given the shape of a planar orthogonal drawing, the task is to place the vertices and the bends on grid points so that the total area or the total edge length is minimised. We compare four constructive heuristics based on rectangular dissection and on turn-regularity, also in combination with two improvement heuristics based on longest paths and network ows, and an exact method which is able to compute provable optimal drawings of minimum total edge length.We provide a performance evaluation in terms of quality and running time. The test data consists of two test-suites already used in previous experimental research. In order to get hard instances, we randomly generated an additional set of planar graphs.

GraphXML is a graph description language in XML that can be used as an interchange format for graph drawing and visualization packages. The generality and rich features of XML make it possible to define an interchange format that not only supports the pure, mathematical description of a graph, but also the needs of information visualization applications that use graph-based data structures.

We introduce polar visibility graphs, graphs whose vertices can be represented by arcs of concentric circles with adjacency determined by radial visibility including visibility through the origin. These graphs are more general than the well-studied bar-visibility graphs and are characterized here, when arcs are proper subsets of circles, as the graphs that embed on the plane with all but at most one cut-vertex on a common face or on the projective plane with all cut-vertices on a common face. We also characterize the graphs representable using full circles and arcs.

The data structure SPQR-tree represents the decomposition of a biconnected graph with respect to its triconnected components. SPQR-trees have been introduced by Di Battista and Tamassia [8] and, since then, became quite important in the field of graph algorithms. Theoretical papers using SPQR-trees claim that they can be implemented in linear time using a modification of the algorithm by Hopcroft and Tarjan [15] for decomposing a graph into its triconnected components. So far no correct linear time implementation of either triconnectivity decomposition or SPQR-trees is known to us. Here, we show the incorrectness of the Hopcroft and Tarjan algorithm [15], and correct the faulty parts. We describe the relationship between SPQR-trees and triconnected components and apply the resulting algorithm to the computation of SPQR-trees. Our implementation is publically available in AGD [1].

We deal with a map-labeling problem, named LOFL (Leftpart Ordered Flexible Labeling), to label a set of points in a plane with polygonal obstacles. The label for each point is selected from a set of rectangles with various shapes satisfying the left-part ordered property, and is placed near to the point after scaled by a scaling factor σ which is common to all points. In this paper, we give an optimal O((n+m) log(n+ m)) algorithm to decide the feasibility of LOFL for a fixed scaling factor σ, and an O((n + m) log2(n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the number of edges of polygonal obstacles.

We show how to utilize the cactus representation of all minimum cuts of a graph to visualize the minimum cuts of a planar graph in a planar drawing. In a first approach the cactus is transformed into a hierarchical clustering of the graph that contains complete information on all the minimum cuts. We present an algorithm for c-planar orthogonal drawings of hierarchically clustered planar graphs with rectangularly shaped cluster boundaries and the minimum number of bends. This approach is then extended to drawings in which the two vertex subsets of every minimum cut are separated by a simple closed curve.

A common strategy in drug design and pharmacophore identification consists of evaluating large sets of molecular structures by comparing their 2D structure drawings. To simplify the chemists’ task, the drawings should reveal similarities and differences between drugs. Given a family of molecules all containing a common template, we present an algorithm to compute standardised 2D structure drawings. The molecules being represented as a graph, we compute a structure called supertree in which all molecules can be embedded. Using the correspondences between atoms provided by the supertree, we are able to coordinate the drawings performed by a breadth-first traversal of the molecular graphs. Both parts of the problem are NP-hard. We propose algorithms of heuristic nature.

Timetable graphs are used to analyze transportation networks. In their visualization, vertex coordinates are fixed to preserve the underlying geography, but due to small angles and overlaps, not all edges should be represented by geodesics (straight lines or great circles).A previously introduced algorithm represents a subset of the edges by Bézier curves, and places control points of these curves using a force- directed approach [5]. While the results are of very good quality, the running times make the approach impractical for interactive systems. In this paper, we present a fast layout algorithm using an entirely different approach to edge routing, based on directions of control segments rather than positions of control points. We reveal an interesting theoretical connection with Tutte’s barycentric layout method [18], and our computational studies show that this new approach yields satisfactory layouts even for huge timetable graphs within seconds.

Statecharts [9] are widely used for the requirements specification of reactive systems. In this paper, we present a framework for the automatic generation of layouts of statechart diagrams. Our framework is based on several techniques that include hierarchical drawing, labeling, and floorplanning, designed to work in a cooperative environment. Therefore, the resulting drawings enjoy several important properties: they emphasize the natural hierarchical decomposition of states into substates; they have a low number of edge crossings; they have good aspect ratio; and require a small area. We have implemented our framework and obtained drawings for several statechart examples. The preliminary drawings are very encouraging.

Hermes is a system for exploring and visualizing Autonomous Systems and their interconnections. It relies on a three-tiers architecture, on a large repository of routing information coming from heterogeneous sources, and on sophisticated graph drawing engine. Such an engine exploits static and dynamic graph drawing techniques.

We report an experience on a practical system for drawing hypergraphs in the subset standard. The Patate system is based on the application of a classical force directed method to a dynamic graph, which is deduced, at a given iteration time, from the hypergraph structure and particular vertex locations. Different strategies to define the dynamic underlying graph are presented. We illustrate in particular the method when the graph is obtained by computing an Euclidean Steiner tree.

Knowledge discovery is the process of discovering useful and previously unknown knowledge by analyzing large databases. Knowledge discovery is also sometimes called “data mining” or “applied machine learning.” A new generation of knowledge discovery tools are beginning to address data that can be expressed as large graphs. Example applications include fraud detection in telecommunication networks and classifying Web pages based on hyperlink structure. These new technologies for knowledge discovery are becoming increasingly relevant to graph drawing. Specifically, graph drawing can aid the process of knowledge discovery by providing visualizations that reveal useful patterns in the data. Conversely, knowledge discovery can provide guidance for graph drawing by identifying recurring substructures or by classifying nodes into distinct types. Attempts to exploit the synergy between the two fields raises interesting new research questions. How should knowledge about a domain affect the drawing of graphs about that domain? What types of knowledge are most easily discovered using visualization, as opposed to automated statistical algorithms? These questions were posed in the context of several examples of knowledge discovery applied to large graphical data sets.

We describe a heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm. The multilevel process groups vertices to form clusters, uses the clusters to define a new graph and is repeated until the graph size falls below some threshold. The coarsest graph is then given an initial layout and the layout is successively refined on all the graphs starting with the coarsest and ending with the original. In this way the multilevel algorithm both accelerates and gives a more global quality to the force- directed placement. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on a number of examples ranging from 500 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 30 seconds for a 10,000 vertex graph to around 10 minutes for the largest graph. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

We present a multi-scale layout algorithm for the aesthetic drawing of undirected graphs with straight-line edges. The algorithm is extremely fast, and is capable of drawing graphs of substantially larger size than any other algorithm we are aware of. For example, the algorithm achieves optimal drawings of 1000 vertex graphs in about 2 seconds. The paper contains graphs with over 6000 nodes. The proposed algorithm embodies a new multi-scale scheme for drawing graphs, which was motivated by the recently published multi-scale algorithm of Hadany and Harel [7]. It can significantly improve the speed of essentially any force-directed method (regardless of that method’s ability of drawing weighted graphs or the continuity of its cost-function).

A fast algorithm(fade) for the 2D drawing, geometric clustering and multilevel viewing of large undirected graphs is presented. The algorithm is an extension of the Barnes-Hut hierarchical space decomposition method, which includes edges and multilevel visual abstraction. Compared to the original force directed algorithm, the time overhead is O(e + n log n) where n and e are the numbers of nodes and edges. The improvement is possible since the decomposition tree provides a systematic way to determine the degree of closeness between nodes without explicitly calculating the distance between each node. Different types of regular decomposition trees are introduced. The decomposition tree also represents a hierarchical clustering of the nodes, which improves in a graph theoretic sense as the graph drawing approaches a lower energy state. Finally, the decomposition tree provides a mechanism to view the hierarchical clustering on various levels of abstraction. Larger graphs can be represented more concisely, on a higher level of abstraction, with fewer graphics on screen.

We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional drawing of the graph is then obtained by projecting a higher-dimensional embedding into a two or three dimensional subspace of E. Projecting high-dimensional drawings onto two or three dimensions often results in drawings that are “smoother” and more symmetric. Among the other notable features of our approach are the utilization of a maximal independent set filtration of the set of vertices of a graph, a fast energy function minimization strategy, efficient memory management, and an intelligent initial placement of vertices. Our implementation of the algorithm can draw graphs with tens of thousands of vertices using a negligible amount of memory in less than one minute on a mid-range PC.

This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. The system is designed for drawing large graphs and uses a novel multi-dimensional force-directed method together with fast energy function minimization. The system allows for drawing graphs with tens of thousands of vertices in under a minute on a mid-range PC. To the best of the authors’ knowledge GRIP surpasses the fastest previous algorithms. However, speed is not achieved at the expense of quality as the resulting drawings are quite aesthetically pleasing.

We present a fast layout algorithm for k-level graphs with given permutations of the vertices on each level. The algorithm can be used in particular as a third phase of the Sugiyama algorithm [8]. In the generated layouts, every edge has at most two bends and is drawn vertically between these bends. The total length of short edges is minimized levelwise.

Displaying a program’s data structures as a graph is a valuable addition to debuggers, however, previous papers have not discussed the layout issues specific to displaying data structures. We find that the semantics of data structures may require constraining node and edge path orderings, and that nonhierarchical, leveled graphs are the preferred data structure display. We describe layout problems for data structures, and extend the Sugiyama algorithm to solve them.

Recently, a technique called sifting has been proposed for k-layer straightline crossing minimization. This approach outperforms the traditional layer by layer sweep based heuristics by far when applied to k-layered graphs with k≥3. In this paper, we present two methods to speed up sifting. First, it is shown how the crossing matrix can be computed and updated efficiently. Then, we study lower bounds which can be incorporated in the sifting algorithm, allowing to prune large parts of the search space. Experimental results show that it is possible to speed up sifting by more than a factor of 20 using the new methods.

In this paper we present the first non-trivial lower bounds for the total number of bends in 3-D orthogonal drawings of maximum degree six graphs. In particular, we prove lower bounds for the number of bends in 3-D orthogonal drawings of complete simple graphs and multigraphs, which are tight in most cases. These result are used as the basis for the construction of infinite classes of c-connected simple graphs and multigraphs (2 ≤c ≤6) of maximum degree Δ (3 ≤Δ ≤6) with lower bounds on the total number of bends for all members of the class. We also present lower bounds for the number of bends in general position 3-D orthogonal graph drawings. These results have significant ramifications for the ‘2-bends’ problem, which is one of the most important open problems in the field.

Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the following problem. Does there exist an orthogonal drawing Γ of C in 3D such that each edge of Γ respects the direction assigned to it and such that Γ does not intersect itself? If the answer is positive, we say that C is simple. This problem arises in the context of extending orthogonal graph drawing techniques and VLSI rectilinear layout techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.

In this paper, we study three-dimensional orthogonal box-drawings of graphs without loops. We provide lower bounds for three scenarios: (1) drawings where vertices have bounded aspect ratio, (2) drawings where the surface of vertices is proportional to their degree, and (3) drawings without any such restrictions. Then we give constructions that match the lower bounds in all scenarios within an order of magnitude.

An orthogonal drawing of a plane graph G is a drawing of G with the given planar embedding in which each vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. Observe that only a planar graph with the maximum degree four or less has an orthogonal drawing. The best known algorithm to find an orthogonal drawing runs in time O(n7/4√log n) for any plane graph with n vertices. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given biconnected cubic plane graph with the minimum number of bends.

In this paper we introduce a number of techniques for the refinement of three-dimensional orthogonal drawings of maximum degree six graphs. We have implemented several existing algorithms for three- dimensional orthogonal graph drawing including a number of heuristics to improve their performance. The performance of the refinements on the produced drawings is then evaluated in an extensive experimental study. We measure the aesthetic criteria of the bounding box volume, the average and maximum number of bends per edge, and the average and maximum edge length. On the same set of graphs used in Di Battista et al. [3], our main refinement algorithm improves the above aesthetic criteria by 80%, 38%, 10%, 54% and 49%, respectively.

A drawing of a graph in the plane is ω-searchlight obedient if every vertex of the graph is located on the centerline of some strip of width ω, which does not contain any other vertex of the graph. We estimate the maximum possible value ω(n) of an ω-searchlight obedient drawing of a graph with n vertices, which is contained in the unit square. We show a lower bound and an upper bound on ω(n), namely, ω(n) = Ω(log n=n) and ω(n) = ω(n) O(1/n4/7−∈), for an arbitrarily small ε > 0. Any improvement for either bound will also carry on to the famous Heilbronn’s triangle problem

A topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by Jordan curves connecting the corresponding points, with the property that any two curves have at most one point in common. We define two canonical classes of topological complete graphs, and prove that every topological complete graph with n vertices has a canonical subgraph of size at least c log log n, which belongs to one of these classes. We also show that every complete topological graph with n vertices has a non- crossing subgraph isomorphic to any fixed tree with at most c log1/6n vertices.

This paper studies the drawability problem for minimum weight triangulations, i.e. whether a triangulation can be drawn so that the resulting drawing is the minimum weight triangulations of the set of its vertices. We present a new approach to this problem that is based on an application of a well known matching theorem for geometric triangulations. By exploiting this approach we characterize new classes of minimum weight drawable triangulations in terms of their skeletons. The skeleton of a minimum weight triangulation is the subgraph induced by all vertices that do not belong to the external face. We show that all maximal triangulations whose skeleton is acyclic are minimum weight drawable, we present a recursive method for constructing infinitely many minimum weight drawable triangulations, and we prove that all maximal triangulations whose skeleton is a maximal outerplanar graph are minimum weight drawable.

We characterize two types of bar-visibility graphs on the Möbius band (abbreviated “BVGMs”), in which vertices correspond to intervals that are parallel or orthogonal to the axis of the band, depending on type, and in which adjacency corresponds to orthogonal visibility of intervals. BVGMs with intervals orthogonal to the axis are shown to be equivalent to the “polar visibility graphs” studied by Hutchinson [7]. BVGMs with intervals parallel to the axis are characterized as those graphs G which satisfy the following conditions: G is embedded on the Möbius band; the block-cutpoint tree of G is a caterpillar in which all but at most one block is planar; and the non-planar block, if it exists, is at the “head” of the caterpillar.

This paper presents a model for drawing trees symmetrically in three dimensions and a linear time algorithm for finding maximum number of three dimensional symmetries in trees.

Let G be an n-node graph. We address the problem of computing a maximum symmetric graph H from G by deleting nodes, deleting edges, and contracting edges. This NP-complete problem arises naturally from the objective of drawing G as symmetrically as possible. We show that its tractability for the special cases of G being a plane graph, an ordered tree, and an unordered tree, depends on the type of operations used to obtain H from G. Moreover, we give an O(log n)-approximation algorithm for the intractable case that H is obtained from a tree G by contracting edges. As a by-product, we give an O(log n)-approximation algorithm for an NP-complete edit-distance problem.

The stability is an essential issue for incremental drawings. To allow stable updating, means to modify graph slightly (such as adding or deleting an edge or a node) without changing the layout dramatically from previous layout. In this paper, a method for achieving stable incremental directed graph layout by using clan-based graph decomposition is described. For a given directed graph, the clan-based decomposition generates a parse tree. The parse tree, which is used for layout, is also employed in locating changes and maintaining visual stability during incremental drawing. By using the generated parse tree, each incremental update can be done very efficiently.

Enabling the user of a graph drawing system to preserve the mental map between two different layouts of a graph is a major problem. In this paper we present Marey, a system that can smoothly transform one drawing of a graph into another without any restrictions to the class of graphs or type of layout algorithm.

Prompted by the increasing demand for a standard exchange format for graph data, an informal workshop was held in conjunction with Graph Drawing 2000. The participants identified requirements for such a standard and formed a group to work out a proposal. The current status of this effort is publicly available at http://www.graphdrawing. org /data /format /.

This report describes the Seventh Annual Graph Drawing Contest, held in conjunction with the 2000 Graph Drawing Symposium in Williamsburg, Virginia. The purpose of the contest is to monitor and challenge the current state of the art in graph-drawing technology [3],[4], [6],[7],[5],[2].