Graph Drawing

We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a crossing-free manner, graphs—such as software interaction diagrams—that would normally have many crossings. The main idea of this approach is quite simple: we allow groups of edges to be merged together and drawn as “tracks” (similar to train tracks). Producing such confluent diagrams automatically from a graph with many crossings is quite challenging, however, so we offer two heuristic algorithms to test if a non-planar graph can be drawn efficiently in a confluent way. In addition, we identify several large classes of graphs that can be completely categorized as being either confluently drawable or confluently non-drawable.

We present an extensive experimental study of heuristics for crossing minimization. The heuristics are based on the planarization approach, so far the most successful framework for crossing minimization. We study the effects of various methods for computing a maximal planar subgraph and for edge re-insertion including post-processing and randomization.

In this paper we give a new description of the planarity testing and embedding algorithm presented by Boyer and Myrvold [2], providing, in our opinion, new insights on the combinatorial foundations of the algorithm. Especially, we give a detailed illustration of a fundamental phase of the algorithm, called walk-up, which was only succinctly illustrated in [2]. Also, we present an implementation of the algorithm and extensively test its efficiency against the most popular implementations of planarity testing algorithms. Further, as a side effect of the test activity, we propose a general overview of the state of the art (restricted to efficiency issues) of the planarity testing and embedding field.

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_{2 k + 1, q}, for k ≥ 2. We prove tight bounds for complete graphs.

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K _n with n vertices under various side conditions.

Intersection graphs of convex polygons inscribed to a circle, so called polygon-circle graphs, generalize several well studied classes of graphs, e.g., interval graphs, circle graphs, circular-arc graphs and chordal graphs. We consider the question how complicated need to be the polygons in a polygon-circle representation of a graph.Let cmp (n) denote the minimum k such that every polygon-circle graph on n vertices is the intersection graph of k-gons inscribed to the circle. We prove that cmp(n) = n − log₂n + o(log₂n) by showing that for every positive constant c < 1,cmp(n) ≤ n − clogn for every sufficiently large n, and by providing an explicit construction of polygon-circle graphs on n vertices which are not representable by polygons with less than n − logn − 2 loglogn corners. We also show that recognizing intersection graphs of k-gons inscribed in a circle is an NP-complete problem for every fixed k ≥ 3.

We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines.

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: Determine a function h, where h(n) is the largest number k such that when we remove arbitrary set of k edges from a complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that $h(n)=\Omega(\sqrt{n})$. We also determine the function exactly in case when the removed edges form a star or a matching, and give asymptotically tight bounds in case they form a clique.

GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration graphs. We also create difference graphs which capture the nature of change between two given time periods. GraphAEL can be accessed online at http://graphael.cs.arizona.edu.

We propose a method for visualizing a set of related metabolic pathways using $2\frac{1}{2}$D graph drawing. Interdependent, two-dimensional layouts of each pathway are stacked on top of each other so that biologists get a full picture of subtle and significant differences among the pathways. Layouts are determined by a global layout of the union of all pathway-representing graphs using a variant of the proven Sugiyama approach for layered graph drawing that allows edges to cross if they appear in different graphs.

The Unified Modeling Language (UML) has become the software industry’s standard notation for representing software architecture and design models. UML diagrams play an important role in the engineering and re-engineering processes of software systems. Of particular interest from the Graph Drawer’s perspective are UML class diagrams whose purpose is to display class hierarchies (generalizations), associations, aggregations, and compositions in one picture. The combination of hierarchical and non-hierarchical relations poses a special challenge to a graph layout tool. We present an implementation of our technology within well-known modelling tools.

We show that an outerplanar graph G with n vertices and degree d admits a planar straight-line grid drawing with area O(dn1.48) in O(n) time. This implies that if d =o(n0.52), then G can be drawn in this fashion in o(n2) area.

In this paper we introduce a framework for producing circular drawings in which the groupings are user-defined. These types of drawings can be used in applications for telecommunications, computer networks, social network analysis, project management, and more. This fast approach produces drawings in which the user-defined groupings are highly visible, each group is laid out with a low number of edge crossings, and the number of crossings between intra-group and inter-group edges is low.

In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n is the number of vertices in the graph. If for every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n2) algorithm to find out if a drawing with no crossings can be realized. We present an improved O(n7/4polylogn) time algorithm. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n3/2polylogn) time. We also consider the problem if we have more than two possible circular arcs per edge and show that the problem becomes NP-Hard. Moreover, we show that two optimization versions of the problem are also NP-Hard.

Trees are usually drawn using planar straight-line drawings. [1] presented an algorithm for constructing a planar straight-line grid drawing of an n-node binary tree with area O(n) and any pre-specified aspect ratio in the range [n − α,nα], where 0 ≤ α < 1 is any constant, in $\mathcal{O}(n {\rm log}n)$ time. Unfortunately, the algorithm of [1] is not suitable for practical use. The main problem is that the constant hidden in the “Oh” notation for area is quite large (e.g., it can be as large as 3900).In this paper, we have made several practical improvements to the algorithm, which make it suitable for practical use. We have also conducted experiments on this newer version of the algorithm for randomly-generated and complete binary trees with up to 50,000, and 65,535 nodes, respectively. Our experiments show that it constructs area-efficient drawings in practice, with area at most 10 times and 8 times the number of nodes for randomly-generated and complete binary trees, respectively.

The problem of exact symmetry detection in general graphs has received much attention recently. In spite of its NP-hardness, two different algorithms have been presented that in general can solve this problem quickly in practice [5,2]. However, as most graphs do not admit any exact symmetry at all, the much harder problem of fuzzy symmetry detection arises: a minimal number of certain modifications of the graph should be allowed in order to make it symmetric. We present a general approach to this problem: we allow arbitrary edge deletions and edge creations; every single modification can be given an individual weight. We apply integer programming techniques to solve this problem exactly or heuristically and give runtime results for a first implementation.

We study barycentric placement of vertices in periodic graphs of dimension 2 or higher. Barycentric placements exist for every connected periodic graph, are unique up to affine transformations, and provide a versatile tool not only in drawing, but also in computation. Example applications include symmetric convex drawing in dimension 2 as well as determining topological types of crystals and computing their ideal symmetry groups.

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A $\mathcal{O}(n^{3/2})$ volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was $\mathcal{O}(n^{2})$. These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

In this paper, we study a layout problem of a digraph using queues. The queuenumber of a digraph is the minimum number of queues required for a queue layout of the digraph. We present upper and lower bounds on the queuenumber of an iterated line digraph Lk(G) of a digraph G. In particular, our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the result on the queuenumber of Lk(G), it is shown that for any fixed digraph G, Lk(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in Lk(G). We also apply these results to particular families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, butterfly digraphs, and wrapped butterfly digraphs.

A k-track drawing is a crossing-free 3D straight-line drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In [9] it is proved that every graph from a proper minor closed family has constant track number if and only if it has constant queue number. In this paper we study the track number of well-known families of graphs with small queue number. For these families we show upper bounds and lower bounds on the track number that significantly improve previous results in the literature. Linear time algorithms that compute track drawings of these graphs are also presented and their volume complexity is discussed.

This paper continues the study of 3D visibility representations of complete graphs where vertices are represented by equal convex polygons lying in planes parallel to the xy-plane. Edges correspond to the z-parallel visibility among these polygons.We give several bounds on the size of the largest complete graph that has a 3D visibility representation with particular properties. Namely we improve the best known lower bound for representations by regular n-gons from $\lfloor \frac{n+1}{2}\rfloor+2$ to n+1 and the upper bound from $2^{2^{n}}$ to $\left({6n-3 \atop 3n-1}\right)-3$.

A k-track drawing is a crossing-free 3D straight-line grid drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In the existing literature a lower bound of five and an upper bound of fifteen are known for the track number of series-parallel graph. In this paper we reduce this gap for a large subclass of series-parallel graph for which the lower bound remains five but we show an upper bound of eight. We also describe a linear time drawing algorithm that computes a 3D straight-line grid drawing of these graphs in volume 4 × 4 × 2n.

In this paper we consider the three-dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three-dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method providing an upper bound on the layout volume of the hypercube network.

We present new linear time algorithms using the SPQR-tree data structure for computing planar embeddings of planar graphs optimizing certain distance measures. Experience with orthogonal drawings generated by the topology-shape-metrics approach shows that planar embeddings following these distance measures lead to improved quality of the final drawing in terms of bends, edge length, and drawing area.Given a planar graph, the algorithms compute the planar embedding with1the minimum depth among the set of all planar embeddings of G,2the external face of maximum size among the set of all planar embeddings of G,3the external face of maximum size among the set of all embeddings of G with minimum depth.

In this paper we give an algorithm to generate all biconnected plane triangulations having exactly n vertices including exactly r vertices on the outer face. The algorithm uses O(n) space in total and generates such triangulations without duplications in O(rn) time per triangulation, while the previous best algorithm generates such triangulations in O(r2n) time per triangulation.

We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the planarity restrictions, which has close connections to rigidity theory, and where it is easy to see that the problem is NP-hard. In contrast, we show that the problem is tractable—indeed, solvable in linear time on a real RAM—for planar embeddings of planar 3-connected triangulations, even if the outer face is not a triangle. This result is essentially tight: the problem becomes NP-hard if we consider instead planar embeddings of planar 3-connected infinitesimally rigid graphs, a natural relaxation of triangulations in this context.

In this paper we describe the visual interface of BGPlay, an on-line service for the visualization of the behavior and of the instabilities of the Internet routing at the autonomous system level.A graph showing only connections among autonomous systems is not enough to convey all the information needed to fully understand the routing and its changes. BGPlay provides specifically tailored techniques and algorithms to show the routing at specific instants of time and to animate its changes. The system obtains routing data from well known on-line archives of routing information constantly kept up-to-date.

The Internet-based translation service GraphEX automatically converting between different graph formats, making it easier for users to take advantage of the full variety of graph drawing tools. GraphEx builds on the prototype translation component of the Graph Drawing Server [2], improving the handling of information mismatch problems and adding support for user-defined formats.

We present a new elegant algorithm for layout of biological signaling pathways. It uses a force-directed layout scheme, taking into account directional and regional constraints enforced by different molecular interaction types and subcellular locations in a cell. The algorithm has been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA and results with respect to computational complexity and quality of the layout have been found satisfactory.

Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar graphs. Our algorithm uses a combination of different techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs. Our algorithm can morph between drawings with straight-line segments, bends, and curves. Our system is implemented in Java and available as an applet at http://gmorph.cs.arizona.edu.

We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [5] and derive an O(1.4656k + kn2) algorithm for this problem, where k upperbounds the number of tolerated crossings of straight lines involved in the drawings of an n-vertex graph. Relations of this graph-drawing problem to the algebraic problem of finding a weighted linear extension of an ordering similar to [7] are exhibited.

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently minimum biplanarizing sets containing up to about 18 edges, thus making it comparable to previous integer linear programming approaches. We show how our implementation slightly improves the theoretical running time to O(6bpr(G) + |G |). Finally, we explain how our experimental work predicts how performance on sparse graphs may be improved.

A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa.We show that the families of cuts that admit a drawing in which every cut is represented by an axis-parallel rectangle are exactly those that have a cactus model that can be rooted such that edges of the graph that cross a cycle of the cactus point to the root. This includes the family of all minimum cuts of a graph. The proof also yields an efficient algorithm to construct a drawing with axis-parallel rectangles if it exists.

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph is a graph with a set of non-intersecting clusters. In this paper, we assume that the graph is planar, each non leaf cluster has exactly two child clusters in the tree representation of non-intersecting clusters, and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight line segments with no crossing between two edges, and (ii) the boundary of the biconnected subgraph induced by each cluster is convex polygon.

We present a layout algorithm for directed hypergraphs. A hypergraph contains hyperedges that have multiple source and target nodes. Hyperedges are drawn with orthogonal segments. Nodes are organized in layers, so that for the majority of hyperedges the source nodes are placed in a higher layer than the target nodes, similar to traditional hierarchical layout [8,11]. The algorithm was implemented using ILOG JViews [10] for a project that targeted electrical signal visualization.

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdividions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

Every planar graph has a concentric representation based on a breadth first search, see [21]. The vertices are placed on concentric circles and the edges are routed as curves without crossings. Here we take the opposite view. A graph with a given partitioning of its vertices onto k concentric circles is k-radial planar, if the edges can be routed monotonic between the circles without crossings. Radial planarity is a generalisation of level planarity, where the vertices are placed on k horizontal lines. We extend the technique for level planarity testing of [18,17,15,16,12,13] and show that radial planarity is decidable in linear time, and that a radial planar embedding can be computed in linear time.

Given a bipartite graph G=(V,W,E), a bilayer drawing consists of placing nodes in the first vertex set V on a straight line L₁ and placing nodes in the second vertex set W on a parallel line L₂. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L₁ so that the number of arc crossings is minimized. In this paper, we prove that there always exits a solution whose crossing number is at most 1.4664 times of a well-known lower bound that is obtained by summing up {c _uv , c _vu } over all node pairs u,vεV, where c _uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering.

We study how to draw a 2-outerplane graph on two concentric circles, so that the internal (resp. external) vertices lie on the internal (resp. external) circle.

We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the best-known force and energy models do not clearly show clusters for graphs whose diameter is small relative to the number of nodes. We formally characterize the minimum energy drawings of our energy model. This characterization shows in what sense the drawings separate clusters, and how the distance of separated clusters to the other nodes can be interpreted.

In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different algorithms for simultaneous graph drawing and three different visualization schemes. The algorithms are based on a modification of the force-directed algorithm that allows us to take into account vertex weights and edge weights in order to achieve mental map preservation while obtaining individually readable drawings. The implementation is in Java and the system can be downloaded at http://simg.cs.arizona.edu/.

Graph drawing algorithms based on minimizing the so-called stress energy strive to place nodes in accordance with target distances. They were first introduced to the graph drawing field by Kamada and Kawai [11], and they had previously been used to visualize general kinds of data by multidimensional scaling. In this paper we suggest a novel algorithm for the minimization of the Stress energy. Unlike prior stress-minimization algorithms, our algorithm is suitable for a one-dimensional layout, where one axis of the drawing is already given and an additional axis needs to be computed. This 1-D drawing capability of the algorithm is a consequence of replacing the traditional node-by-node optimization with a more global axis-by-axis optimization. Moreover, our algorithm can be used for multidimensional graph drawing, where it has time and space complexity advantages compared with other stress minimization algorithms.

A potential field approach, coupled with force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly or nonuniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. Our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of graphs in 2-D and 3-D can be produced efficiently.

We consider the problem of drawing Venn diagrams for which each region’s area is proportional to some weight (e.g., population or percentage) assigned to that region. These area-proportional Venn diagrams have an enhanced ability over traditional Venn diagrams to visually convey information about data sets with interacting characteristics. We develop algorithms for drawing area-proportional Venn diagrams for any population distribution over two characteristics using circles and over three characteristics using rectangles and near-rectangular polygons; modifications of these algorithms are then presented for drawing the more general Euler diagrams. We present results concerning which population distributions can be drawn using specific shapes. A program to aid further investigation of area-proportional Venn diagrams is also described.

A pants decomposition of a compact orientable surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross.We give an algorithm which, given a pants decomposition, computes a homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all homotopic pants decompositions), and any optimal pants decomposition is made of shortest homotopic cycles. Our algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle homotopic to C which is itself simple.

In this paper, we follow the evolution of a tool that has its roots in academic research on visualization and graph drawing. From its ancestor Order Explorer (1994) and initial version of 1995, to its latest version of 2003, we analyze the significant steps of a software that has gone from being a relatively simple, very specialized research tool to being a successful, widely deployed, complex commercial software used for academic degree audits. As the tool has expanded over the years, the initial scope has been completely outgrown and finding back the original idea in the current version is not completely obvious. Never the less, Degree NavigatorTM is a wonderful example of a research project that has gone a long way.

Hex [1] is a two player board game which is traditionally played on a rhombic hexagonal pattern (See Figure (1)). Players are assigned a colour and make moves by putting a token of their colour onto an empty field on the board. The first player to connect the two borders of the board in his colour by a path of his tokens on the board wins the game. Alternatively, Hex is played on an undirected, tricoloured (Red, Blue, Unclaimed) graph G [2]. The fields are represented by nodes and adjacent fields on the board are connected by an edge. The four borders of the board are represented by one node of equivalent colour each (See Figure(1)).

GLuskap

In recent years, link-based information retrieval methods from the Web are developed, such as HITS and Trawling. Since these methods utilize characteristic graph structures of links in the Web, analyzing the links by drawing them understandably will play an important role in the link-based information retrieval. Moreover, Asano et al.[2], [3] have shown that a framework using a site as a unit of information is more natural and useful for link-based information retrieval than the existing framework using a page as a unit. Therefore, we should distinguish links inside a site (called local-links) between links between sites (called global-links) and analyze their own graph structures. However, existing drawing tools, such as Gravis [1] and H3Viewer[5], do not distinguish local-links between global-links, and therefore they cannot draw graph structures of these links understandably. In this paper, we propose a new drawing tool, named Web-linkage Viewer, in order to draw graph structures in the Web according to the site-oriented framework.

This poster describes an implementation of the puzzle generators and puzzle layouts introduced in [1].

Data mining deals with the discovery of useful and previously unknown knowledge from large data sets [3]. Traditional data mining tools use a combination of machine learning, statistical analysis, modeling techniques and database technology to find patterns, exceptions and subtle relationships in data. Typical applications include market segmentation, customer profiling, fraud detection, credit risk analysis, and business data development.

This report describes the Tenth Annual Graph Drawing Contest, held in conjunction with the 2003 Graph Drawing Symposium in Perugia, Italy. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology.

We discuss some relevant issues in Algorithm Engineering, focussing on the interplay between theory and practice,and showing how it can integrate and reinforce the traditional theoretical approaches to the design and analysis of algorithms and data structures,while de- vising methodologies and tools for developing and engineering e .cient algorithmic codes.

The invited lecturer Pat Hanrahan is a professor at the Computer Science Department of Stanford University, Stanford CA 94305-9025, USA.The talk given by Prof. Hanrahan was about the connection between semantic constraints and aesthetics in graph drawing and information visualization. Examples were given of different application contexts where, in order to convey the right semantic information in a diagram, it is essential to respect geometric constraints concerning the shape of the edges and /or the relative position of the vertices. These examples include drawing maps (such as the map of the metro), visualizing (portions of) the Internet, and representing chemical maps.

In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.