Graph Drawing

Given a tree T on n vertices and a set P of n points in the plane in general position, it is known that T can be straight line embedded in P without crossings. Now imagine the set P is partitioned into two disjoint subsets R and B, and we ask for an embedding of T in P without crossings and with the property that all edges join a point in R (red) and a point in B (blue). In this case we say that T admits a bipartite embedding with respect to the bipartition (R, B). Examples show that the problem in its full generality is not solvable. In view of this fact we consider several embedding problems and study for which bipartitions they can be solved. We present several results that are valid for any bipartition (R, B) in general position, and some other results that hold for particular configurations of points.

The pagenumber of a series-parallel planar P is at most two. We present an O(n3) algorithm to construct a two-page embedding in the case that it is a lattice. One consequence of independent interest, is a characterization of series-parallel planar ordered sets.

We study the problem of drawing a graph in the plane so that the vertices of the graph are rectangles that are aligned with the axes, and the edges of the graph are horizontal or vertical lines-of-sight. Such a drawing is useful, for example, when the vertices of the graph contain information that we wish displayed on the drawing; it is natural to write this information inside the rectangle corresponding to the vertex. We call a graph that can be drawn in this fashion a rectangle-visibility graph, or RVG. Our goal is to find classes of graphs that are RVGs. We obtain several results:1.For 1 ≤ k ≤ 4, k-trees are RVGs.2.Any graph that can be decomposed into two caterpillar forests is an RVG.3.Any graph whose vertices of degree four or more form a distance-two independent set is an RVG.4.Any graph with maximum degree four is an RVG. Our proofs are constructive and yield linear-time layout algorithms.

Both practitioners and researchers can take better advantage of the latest developments in graph drawing if implementations of graph drawing algorithms are made available on the WWW. We envision a graph drawing and translation service for the WWW with dual objectives: drawing user-specified graphs, and translating graph-descriptions and graph drawings from one format to another. As a first step toward realizing this vision, we have developed a prototype service which is available at http://loki.cs.brown.edu:8081/graphserver/home.html.

A Fary grid drawing of a graph is a drawing on a three-dimensional grid such that vertices are placed at integer coordinates and edges are straight-lines such that no edge crossings are allowed.In this paper it is proved that each k-colorable graph (k ≥ 2) needs at least Ω(n3/2)x volume to be drawn. Furthermore, it is shown how to draw 2-, 3- and 4-colorable graphs in a Fary grid fashion in O(n2) volume.

We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation.” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.

In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimental study on four drawing algorithms specifically developed for DAGs. Our study is conducted on two large test suites of DAGs and yields more than 30 charts comparing the performance of the drawing algorithms with respect to several quality measures, including area, crossings, bends, and aspect ratio. The algorithms exhibit various trade-offs with respect to the quality measures, and none of them clearly outperforms the others.

The Graph Layout Toolkit is a family of portable, automated, graph layout libraries designed for integration into graphical user interface application programs. The Circular Library is one of the four styles currently available with the Graph Layout Toolkit. It produces layouts that emphasize natural group structures inherent in a graph's topology, and is well suited for the layout of ring and star network topologies. It clusters (groups) the nodes of a graph by group IDs, by IP addresses, and by biconnectivity or node degree, and allows the user to specify a range for the size of each cluster. The Library positions the nodes of a cluster on a radiating circle, and employs heuristics to reduce the crossings not only between edges incident to nodes of the same cluster but also between edges that connect different clusters.

Clustered graphs are graphs with recursive clustering structures over the vertices. This type of structure appears in many systems. Examples include CASE tools, management information systems, VLSI design tools, and reverse engineering systems. Existing layout algorithms represent the clustering structure as recursively nested regions in the plane. However, as the structure becomes more and more complex, two dimensional plane representations tend to be insufficient. In this paper, firstly, we describe some two dimensional plane drawing algorithms for clustered graphs; then we show how to extend two dimensional plane drawings to three dimensional multilevel drawings. We consider two conventions: straight-line convex drawings and orthogonal rectangular drawings; and we show some examples.

Hierarchical graphs and clustered graphs are useful nonclassical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization, VLSI design, etc. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of straight-line representation has not been addressed. In this paper, we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in O(n2) time. Also, we answer a basic question for clustered graphs, i.e. does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? A method for such drawings is provided in this paper.

This report describes the the Third Annual Graph Drawing Contest, held in conjunction with the 1996 Graph Drawing Symposium in Berkeley, California. The purpose of the contest is to monitor and challenge the current state of the art in graph-drawing technology.

We use basic results from graph theory to design two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(√n× O(√n) × O(√n) box; each edge route contains at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n)×O(n) × O(n) bounding box. Together, the two algorithms initiate the study of bend/bounding box trade-off issues for 3-dimensional grid drawings.

In a 2-visibility drawing the vertices of a given graph are represented by rectangular boxes and the adjacency relations are expressed by horizontal and vertical lines drawn between the boxes. In this paper we want to emphasize this model as a practical alternative to other representations of graphs, and to demonstrate the quality of the produced drawings. We give several approaches, heuristics as well as provably good algorithms, to represent planar graphs within this model. To this, we present a polynomial time algorithm to compute a bend-minimum orthogonal drawing under the restriction that the number of bends at each edge is at most 1.

This paper analyzes the exact and asymptotic worst-case complexity of the simplification phase of Sugiyama's algorithm [12] for drawing arbitrary directed graphs.The complexity of this phase is determined by the number of hidden nodes inserted. The best previously known upper bound for this number is O(max{¦V¦3,¦E¦2}). This paper establishes a relation between both partial results and gives upper bounds for many classes of graphs. This is achieved by constructing a worst-case example for every legal configurationC=(h, n, m) of the input hierarchy for the simplification phase. These results provide further insight into the worst-case runtime and space complexity of Sugiyama's algorithm. Possible applications include their use as feasibility criteria, based on simply derived quantitative information on the graph.

This demonstration shows the Gold system, an extensible software architecture integrating several declarative layout strategies, including springembedders, local constraints and genetic algorithms. The underlying paradigm is to consider graph layout problems as geometric constraint satisfaction problemsIn addition to satisfying global aesthetics criteria, the system allows for the interactive specification of local criteria per vertex (edge).

Hierarchical structures represented by directed acyclic graphs are widely used in visualization applications (e.g., class inheritance diagrams and scheduling diagrams). 3D information visualization has received increasing attention in the last few years, motivated by the advances in hardware and software technology for 3D computer graphics. We present GIOTTO3D, a system for visualizing hierarchical structures in 3D. GIOTTO3D uses a new technique combining 2D drawing methods with a lifting transformation that exploits the third dimension to visualize hierarchical relations among the vertices. GIOTTO3D also employs several graphical aids such as user-defined coloring, showing/hiding subhierarchies, “footprints”, and representation of edges as “Bezier tubes” to improve the effectiveness of its visualizations.

Let N be a single-source single-sink flow network with n nodes, m arcs, and positive arc costs. We present a pseudo-polynomial algorithm that computes a maximum flow of minimum cost for N in time O(χ3/4m√log n), where χ is the cost of the flow. This improves upon previously known methods for networks where the minimum cost of the flow is small. We also show an application of our flow algorithm to a well-known graph drawing problem. Namely, we show how to compute a planar orthogonal drawing with the minimum number of bends for an n- vertex embedded planar graph in time O(n7/4√log n). This is the first subquadratic algorithm for bend minimization. The previous best bound for this problem was O(n2 log n) [19].

Most current graph layout technology does not lend itself to interactive applications such as animation or advanced user interfaces. We introduce the constrained graph layout model which is better suited for interactive applications. In this model, input to the layout module includes suggested positions for nodes and constraints over the node positions in the graph to be layed out. We describe three implementations of layout modules which are based on the constrained graph layout model. The first two implementations are for undirected graph layout and the third is for tree layout. The implementations use active set techniques to solve the layout. Our empirical evaluation shows that they are quite fast and give reasonable layout.

Graphlet is a portable, object oriented toolkit for graph editors and graph drawing algorithms, and is the successor of the GraphEd system. Graphlet is based on LEDA and Tcl/Tk. Algorithms can be implemented in C++ and LedaScript, a new scripting language based on Tcl/Tk. The GML format is a portable file format for graphs.

Let G(V, E) be a graph, and let f: G → R2 be a one to one function that produces a layout of a graph G on the plane. We consider the problem of assigning text labels to every edge of the graph such that the quality of the labeling assignment is optimal. This problem has been first encountered in automated cartography and has been referred to as the Line Feature Label Placement (LFLP) problem. Even though much effort has been devoted over the last 15 years in the area of automated drawing of maps, the Edge Label Placement (ELP) problem has received little attention. In this paper we investigate computational complexity issues of the ELP problem, which have been open up to the present time. Specifically we prove that the ELP problem is NP-Hard.

Arc-connected sets A, B ⊂E₂ are called noncrossing if both A-B and B-A are arc-connected. A graph is called an NCAC graph if it has an intersection representation in which vertices are represented by arc-connected sets in the plane and any two sets of the representation are noncrossing. In particular, disk intersection graphs are NCAC. By a unified reduction we show that recognition of disk intersection and NCAC graphs are NP-hard. A simple observation shows that triangle-free disk intersection and NCAC graphs are planar, and hence recognizable in polynomial time. On the other hand, recognition of triangle-free AC graphs (intersection graphs of arc-connected sets) is still NP-hard.

We consider the wiring or layer assignment problem for edge-disjoint layouts. The wiring problem is well understood for the case that the underlying layout graph is a square grid (see [8]). In this paper, we introduce a more general approach to this problem. For an edge-disjoint layout in the plane resp. in an arbitrary planar layout graph, we give equivalent conditions for the k-layer wirability. Based on these conditions, we obtain linear-time algorithms to wire every layout in a trihexagonal grid, respectively every layout in a tri-square-hexagonal grid using at most five layers.

A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn relatively far apart. The fundamental question concerning proximity drawability is: Given a graph G and a definition of proximity, is it possible to construct a proximity drawing of G? We consider this question for outerplanar graphs with respect to an infinite family of proximity drawings called β-drawings. These drawings include as special cases the well-known Gabriel drawings (when β=1), and relative neighborhood drawings (when β=2). We first show that all biconnected outerplanar graphs are β-drawable for all values of β such that 1 ≤ β ≤ 2. As a side effect, this result settles in the affirmative a conjecture by Lubiw and Sleumer [15, 17], that any biconnected outerplanar graph admits a Gabriel drawing. We then show that there exist biconnected outerplanar graphs that do not admit any convex β-drawing for 1 ≤ β ≤ 2. We also provide upper bounds on the maximum number of biconnected components sharing the same cut-vertex in a β-drawable connected outerplanar graph. This last result is generalized to arbitrary connected planar graphs and is the first non-trivial characterization of connected β-drawable graphs. Finally, a weaker definition of proximity drawings is applied and we show that all connected outerplanar graphs are drawable under this definition.

A two-dimensional cellular complex is a partition of a surface into a finite number of elements—faces (open disks), edges (open arcs), and vertices (points). The topology of a cellular complex is the abstract incidence and adjacency relations among its elements. Here we describe a program that, given only the topology of a cellular complex, computes a geometric realization of the same—that is, a specific partition of a specific surface in three-space—guided by various aesthetic and presentational criteria.

A common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that the number of crossings is minimized. We suggest an alternative method for the second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we address the case k=2. First, we give a motivation for our approach. Then, we address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard. Based on a characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope $$2\mathcal{L}\mathcal{P}\mathcal{S}$$ (G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimension and that the inequalities occuring in the integer linear description are facet-defining for $$2\mathcal{L}\mathcal{P}\mathcal{S}$$ (G). The inequalities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inequalities that substantially improve the quality of the obtained solution. We report on first computational results.

Given a graph G=(V, E), four distinct vertices u₁,u₂,u₃,u₄ ∈ V and four natural numbers n₁, n₂, n₃, n₄ such that $$\sum\nolimits_{i = 1}^4 {n_i = |V|}$$ , we wish to find a partition V₁, V₂, V₃, V₄ of the vertex set V such that u_i ∈ V_i, ¦V_i¦=n_i and V_i induces a connected subgraph of G for each i, 1 ≤ i ≤ 4. In this paper we give a simple linear-time algorithm to find such a partition if G is a 4-connected planar graph and u₁, u₂, u₃, u₄ are located on the same face of a plane embedding of G. Our algorithm is based on a “4-canonical decomposition” of G, which is a generalization of an st-numbering and a “canonical 4-ordering” known in the area of graph drawings.

We show that if a graph of v vertices can be drawn in the plane so that every edge crosses at most k> 0 others, then its number of edges cannot exceed 4.108√kv. For k≤ 4, we establish a better bound, (k + 3)(u− 2), which is tight for k=1 and 2. We apply these estimates to improve a result of Ajtai et al. and Leighton, providing a general lower bound for the crossing number of a graph in terms of its number of vertices and edges.

An orthogonal drawing of a graph is a drawing such that vertices are placed on grid points and edges are drawn as sequences of vertical and horizontal segments. In this paper we present linear time algorithms that produce orthogonal drawings of graphs with n nodes. If the maximum degree is four, then the drawing produced by our first algorithm needs area no greater than 0.76n2, and introduces no more than 2n + 2 bends. Also, every edge of such a drawing has at most two bends. Our algorithm is based on forming and placing pairs of vertices of the graph. If the maximum degree is three, then the drawing produced by our second algorithm needs at most 1/4n2 area, and at most ILn/2 + 2l + 1⌋ bends (⌊n/2⌋ + 3 bends, if the graph is biconnected), where l is the number of biconnected components that are leaves in the block tree. For biconnected graphs, this algorithm produces optimal drawings with respect to the number of bends (within a constant of two), since there is a lower bound of n/2 + 1 in the number of bends for orthogonal drawings of degree 3 graphs.

Interactive Graph Drawing allows the user to dynamically interact with a drawing as the design progresses while preserving the user's mental map. This paper presents a theoretical analysis of Relative-Coordinates and an extensive experimental study comparing the performance of two interactive orthogonal graph drawing scenaria: No-Change, and Relative-Coordinates. Our theoretical analysis found that the Relative-Coordinates scenario builds a drawing that has no more than 3n−1 bends, while the area of the drawing is never larger than 2.25n2. Also, no edge has more than 3 bends at any time during the drawing process. To conduct the experiments, we used a large set of test data consisting of 11,491 graphs (ranging from 6 to 100 nodes) and compared the behavior of the above two scenaria with respect to various aesthetic properties (e.g., area, bends, crossings, edge length, etc) of the corresponding drawings. The Relative-Coordinates scenario was a winner over No-Change under any aesthetic measure considered in our experiments. Moreover, the practical behavior of the two scenaria was considerably better than the established theoretical bounds, in most cases.

In spite of great advances in the automatic drawing of medium and large graphs, the tools available for drawing small graphs exquisitely (that is, with the aesthetics commonly found in professional publications and presentations) are still very primitive. Commercial tools such as Claris Draw or Microsoft's Powerpoint provide minimal support for aesthetic graph layout. At the other extreme, research prototypes based on constraint methods are overly general for graph drawing. Our system improves on general constraint-based approaches to drawing and layout by supporting only a small set of “macro” constraints that are specifically suited to graph drawing. These constraints are enforced by a generalized spring algorithm. The result is a usable and useful tool for drawing small graphs easily and nicely.

We present a new, easy to understand algorithm and programming environment allowing for the interactive or automatic clustering of graphs according to several heuristics.Our approach is based on graph structure only and can be implemented to run efficiently with a personal computer. It is capable of efficiently clustering graphs with > 3000 vertices. We shall demonstrate the interactive user environment for automatic clustering. As an application, we consider the clustering of large WWW connectivity graphs.

Many techniques and algorithms have been proposed for layout and interactions with basic node and link graphs. Here we consider layout and focusing techniques for attributed graphs and show an application of these techniques in a Bellcore system for support of business process design and reengineering called ShowBiz. ShowBiz supports two primary visualization techniques for qualitative analysis of flowgraphs. The first involves the use of parsing to perform graph reduction for encapsulation and focusing. The second is an attributed graph layout technique we have called RB-layout in recognition of its genesis in Rummler-Brache methodology for business process reengineering [7]. The user selects attributes that partition the set of nodes in the graph and the system generates layouts in which the position of the nodes is determined by the value of the attribute in question.