Graph Drawing

A graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. In this paper we consider the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time (real RAM) algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but none of which is Delaunay drawable—that is, drawable as a Delaunay triangulation.

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log3n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [GMPP91, CU96] that requires O(n2) time. Our algorithm is near-optimal as there is an Ω(n log n) lower bound for the problem [BMS95]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where log n ≤ d ≤ 2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(n log n) and O(n2) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(n log n) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.

Let G = (V₀, V₁, E) be a connected bipartite graph, where V₀, V₁ is the bipartition of the vertex set V(G) into independent sets. A bipartite drawing of G consists of placing the vertices of V₀ and V₁ into distinct points on two parallel lines x_o, x₁, respectively, and then drawing each edge with one straight line segment which connects the points of x₀ and x₁ where the endvertices of the edge were placed. The bipartite crossing number of G, denoted by bcr(G) is the minimum number of crossings of edges over all bipartite drawings of G. We develop a new lower bound method for estimating bcr(G). It relates bipartite crossing numbers to edge isoperimetric inequalities and Laplacian eigenvalues of graphs. We apply the method, which is suitable for “well structured” graphs, to hypercubes and 2-dimensional meshes. E.g. for the n-dimensional hypercube graph we get n4n−2−O(4n) ≤ bcr(Q_n) ≤ n4n−1. We also consider a more general setting of the method which uses eigenvalues, but as a trade-off for generality, often gives weaker results.

A three-dimensional grid drawing of a graph G is a placement of the vertices at distinct integer points so that the straight-line segments representing the edges of G are pairwise non-crossing. It is shown that for any fixed r ≥ 2, every r-colorable graph of n vertices has a three-dimensional grid drawing that fits into a box of volume O(n2). The order of magnitude of this bound cannot be improved.

We present two algorithms for orthogonal graph drawing in three dimensional space. For graphs of maximum degree six, the 3-D drawing is produced in linear time, has volume at most 4.66n3 and each edge has at most three bends. If the degree of the graph is arbitrary, the vertices are represented by solid 3-D boxes whose surface is proportional to their degree. The produced drawing has two bends per edge. Both algorithms guarantee no crossings and can be used under an interactive setting (i.e., vertices arrive and enter the drawing on-line), as well.

In this paper we deal with the layout of interconnection networks on three-dimensional grids. In particular, in the first part we prove a general formula for calculating an exact value for the lower bound on the volume. Then we introduce the new notion of k-3D double channel routing and we use it to exhibit an optimal three-dimensional layout for butterfly networks. Finally, we show a method to lay out multigrid and X-tree networks in optimal volume.

This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, Kn in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the bounding box of such drawings and exhibits a construction that achieves this bound. No edge route in this unconstrained construction bends more than three times.For drawings constrained to have at most k bends on any edge route, simple constructions are given for k = 1 and k = 2. The unconstrained construction handles the k ≥ 3 cases, while for k = 0 (no bends), it is proved here that not all graphs can be drawn.

In this paper we address the problem of finding the best viewpoints for three-dimensional straight-line graph drawings. We define goodness in terms of preserving the relational structure of the graph, and develop two continuous measures of goodness under orthographic parallel projection. We develop Voronoi variants to find the best viewpoints under these measures, and present results on the complexity of these diagrams.

An orthogonal drawing of a plane graph G is a drawing of G in which each edge is drawn as a sequence of alternate horizontal and vertical line segments. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n7/4√log n) for any plane graph of n vertices.

Incremental graph drawing is a model gaining more and more importance in many applications. We present algorithms that allow insertions of new vertices into an existing drawing without changing the position of the objects drawn so far. We prove bounds for the quality of our drawings and considerably improve on previous bounds. Here the number of bends and the used area are our quality measures. Besides we discuss lower bounds for this problem.

This paper is devoted to the study of graph embeddings in the grid of non-planar surfaces. We provide an adequate model for those embeddings and we study the complexity of minimizing the number of bends. In particular, we prove that testing whether a graph admits a rectilinear (without bends) embedding essentially equivalent to a given embedding, and that given a graph, testing if there exists a surface such that the graph admits a rectilinear embedding in that surface are NP-complete problems and hence the corresponding optimization problems are NP-hard.

We report on some extensions of the Kandinsky model: A new and highly nontrivial technique to incorporate nonplanar drawings into the Kandinsky model in the same way as in the GIOTTO approach is presented. This means a major step towards the practical usability of our approach. The used technique even gives new insights for the solvability of network flow problems. Another variant of Kandinsky ensures a minimal size of the vertices removing the requirement of uniform size of each vertex. We present a new technique to evaluate our approach with respect to the area and the number of bends, and to perform a reasonable comparison with the GIOTTO approach.

Clustered graphs are graphs with recursive clustering structures over the vertices. For graphical representation, the clustering structure is represented by a simple region that contains the drawing of all the vertices which belong to that cluster. In this paper, we present an algorithm which produces planar drawings of clustered graphs in a convention known as orthogonal grid rectangular cluster drawings. We present an algorithm which produces such drawings with On2 area and with at most 3 bends in each edge. This result is as good as existing results for classical planar graphs. Further, we show that our algorithm is optimal in terms of the number of bends in each edge.

A graph is a cycle of cliques, if its set of vertices can be partitioned into clusters, such that each cluster is a clique and the cliques form a cycle. Then there is a partition of the set of edges into inner edges of the cliques and interconnection edges between the clusters. Cycles of cliques are a special instance of two-level clustered graphs. Such graphs are drawn by a two phase method: draw the top level graph and then browse into the clusters. In general, it is NP-hard whether or not a graph is a two-level clustered graph of a particular type, e.g. a clique or a planar graph or a triangle of cliques. However, it is efficiently solvable whether or not a graph is a path of cliques or is a large cycle of cliques.

Let G(V, E) be a graph, and let Γ be the drawing of G on the plane. We consider the problem of assigning text labels to every edge of G such that the quality of the label assignment is optimal. This problem has been first encountered in automated cartography. 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 remains essentially unsolved. In this paper we investigate the ELP problem. We present an algorithm for the ELP problem more suitable for hierarchical drawings of graphs, but it can be adopted to many different drawing styles and still remain effective. Also, we present experimental results of our algorithm that indicate its effectiveness.

One of the most challenging tasks of cartographic map lettering is the optimal placement of region information on a map. We propose as an approach to this task the elastic labeling problem, in which we are given a set of elastic rectangles as labels, each associated with a point in the plane. An elastic rectangle has a specified area but its width and height may vary. The problem then is to choose the height and width of each label, and the corner of the label to place at the associated point, so that no two labels overlap.This problem is known to be NP-hard even when there is no elasticity (just because of the choice of the corners). We show that the problem remains NP-hard when we have elasticity but no choice about which corner of the label to use—we call this the one-corner elastic labeling problem. We give a polynomial time algorithm for the special case of the one-corner elastic labeling problem in which the points lie on the positive x and y axes and the labels lie in the first quadrant. We call this the two-axis labeling problem.

A number of erroneous attempts involving PQ-trees in the context of automatic graph drawing algorithms have been presented in the literature in recent years. In order to prevent future research from constructing algorithms with similar errors we point out some of the major mistakes.In particular, we examine erroneous usage of the PQ-tree data structure in algorithms for computing maximal planar subgraphs and an algorithm for testing leveled planarity of leveled directed acyclic graphs with several sources and sinks.

A geometric graph is a graph G = (V, E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight line segments between points of V. It is known that, for any fixed k, any geometric graph G on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. In this paper we give a new, simpler proof of this bound, and show that the same bound holds also when the edges of G are represented by x-monotone curves (Jordan arcs).

In this paper, we investigate area requirements for drawing s-t hierarchically planar graphs by straight-lines. Two drawing standards will be discussed: 1) each vertex is represented by a point and 2) grid visibility representation (that is, a line segment is allowed to represent a vertex). For the first drawing standard, we show an exponential area lower bound needed for drawing hierarchically planar graphs. The lower bound holds even for hierarchical graphs without transitive arcs, in contrast to the results for upward planar drawing. Applications of some existing algorithms from upward drawing can guarantee the quadratic drawing area for grid visibility representation but do not necessarily guarantee the minimum drawing area. Motivated by this, we will present another grid visibility drawing algorithm which is efficient and guarantees the minimum drawing area.

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence.C.F. Gauss conjectured (2] that such sequences could be characterized by their interlacement properties. This conjecture was proved by P. Rosenstiehl in 1976 [15]. We shall give here a simple self-contained proof of his characterization. This new proof relies on the D-switch operation.

Dynamic graph layout refers to the layout of graphs that change over time. These changes are due to user interaction, algorithms, or other underlying processes determining the graph. Typically, users spend a noteworthy amount of time to get familiar with a layout, i.e. they build a mental map [ELMS91]. To retain this map at least partially, consecutive layouts of similar graphs should not differ significantly. Still, each of these layouts should adhere to constraints and criteria that have been specified to improve meaning and readability of a drawing.In [BW97], we introduced random field models for graph layout. As a major advantage of this formulation, many different layout models can be represented uniformly by random variables. This uniformity enables us to now present a framework for dynamic layout of arbitrary random field models. Our approach is based on Bayesian decision theory and formalizes common sense procedures. Example applications of our framework are dynamic versions of two well-known layout models: Eades' spring embedder [Ead84], and Tamassia's bend-minimum orthogonal layout model for plane graphs [Tam87].

In the creation of graph drawing algorithms and systems, designers claim that by producing layouts that optimise certain aesthetic qualities, the graphs are easier to understand. Such aesthetics include maximise symmetry, minimise edge crosses and minimise bends.A previous study aimed to validate these claims with respect to three aesthetics, using paper-based experiments [11]. The study reported here is superior in many ways: five aesthetics are considered, attempts are made to place a priority order on the relative importance of the aesthetics, the experiments are run on-line, and the ease of understanding the drawings is measured in time, as well as in the number of errors. In addition, greater consideration is given to the possible effect of confounding factors in the graph drawings.The results indicate that reducing the number of edge crosses is by far the most important aesthetic, while minimising the number of bends and maximising symmetry have a lesser effect. The effects of maximising the minimum angle between edges leaving a node and of fixing edges and nodes to an orthogonal grid are not statistically significant.This work is important since it helps to demonstrate to algorithm and system designers the aesthetic qualities most important for aiding human understanding, the most appropriate compromises to make when there is a conflict in aesthetics, and consequently, how to build more effective systems.

Although routing is a well-studied problem in various contexts, there remain unsolved problems in routing edges for graph layouts. In contrast with techniques from other domains such as VLSI CAD and robotics, where physical constraints play a major role, aesthetics play the more important role in graph layout. For graphs, we seek paths that are easy to follow and add meaning to the layout. We describe a collection of aesthetic attributes applicable to drawing edges in graphs, and present a general approach for routing individual edges subject to these principles. We also give implementation details and survey difficulties that arise in an implementation.

The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which subgraphs exist for which the only possible layouts are rigid. In this paper we introduce an extension called the wobbly logic engine which can be used to prove the NP-hardness of several graph representations for which no such rigid layouts exist, representations by visibility and intersection in particular. We illustrate the method by using the wobbly technique to show the NP-hardness of deciding whether a graph has a nondegenerate z-axis parallel visibility representation (ZPR) by unit squares.

In this paper we describe a tool that is a general frame for the three-dimensional representation of graphs, especially devoted to the algorithms evaluation, refinement and development. 3DCube (3D Diagram Drawer) offers innovative features in the user interaction and contains a set of three-dimensional algorithms both taken from the literature and proposed by the authors.

Identifying the natural clusters of nodes in a graph and treating them as supernodes or metanodes for a higher level graph (or an abstract graph) is a technique used for the reduction of visual complexity of graphs with a large number of nodes. In this paper we report on the implementation of a clustering algorithm based on the idea of ratio cut, a well known technique used for circuit partitioning in the VLSI domain. The algorithm is implemented in WINDOWS95/NT environment. The performance of the clustering algorithm on some large graphs obtained from the archives of Bell Laboratories is presented.

We present ArchE (Archaeological Editor), a system for processing and displaying archaeological data. ArchE checks these data for consistency, simplifies and displays them; for each of these steps ArchE offers a number of different algorithms. The interactive features (eg input, data editing and modification of the layout) are easy to handle. Furthermore, ArchE contains algorithms for focusing on user-defined aspects of the data.Apart from archaeological applications, ArchE can be used as a general graph drawing system.

We present InteractiveGiotto, an interactive algorithm for orthogonal graph drawing based on the network flow approach to bend minimization.

In this paper we present a new interactive tool for computing orthogonal grid drawings of planar graphs. The tool is based on GDToolkit, an object-oriented library of classes for handling graphs and computing their layout. GDToolkit is built on LEDA (an efficient library of data types and algorithms) and currently implements three orthogonal layout methods. Especially, we provide a new branch-and-bound algorithm choosing a planar embedding in order to minimise the number of bends. The enumeration schema of the branch-and-bound algorithm is based on the GDToolkit SPQR-tree class (as far as we know, the only existing SPQR-tree implementation). The tool offers an interactive graphical interface to the branch-and-bound algorithm, which allows to edit the embedding, to execute the algorithm step by step and to view partial results. It also gives quality measures on the drawing, and quantitative measures on the algoritm's performance.

Query refinement is a powerful tool for a document search and retrieval system. Lexical navigation—that is, the exploration of a network that expresses relations among all possible query terms—provides a natural mechanism for query refinement. An essential part of lexical navigation is the visualization of this network. This dynamic visualization problem is essentially one of incrementally drawing and manipulating a non-hierarchical graph. In this paper, we present the graph-drawing system we have developed for lexical navigation.

Many problems in computer-aided design and graphics involve the process of setting and adjusting input parameters to obtain desirable output values. Exploring different parameter settings can be a difficult and tedious task in most such systems. In the Design GalleryTM (DG) approach, parameter setting is made easier by dividing the task more equitably between user and computer. DG interfaces present the user with the broadest selection, automatically generated and organized, of perceptually different designs that can be produced by varying a given set of input parameters. The DG approach has been applied to several difficult parameter-setting tasks from the field of computer graphics: light selection and placement for image rendering; opacity and color transfer-function specification for volume rendering; and motion control for articulated-figure and particle-system animation. The principal technical challenges posed by the DG approach are dispersion (finding a set of input-parameter vectors that optimally disperses the resulting output values) and arrangement (arranging the resulting designs for easy browsing by the user). We show how effective arrangement can be achieved with 2D and 3D graph drawing. While navigation is easier in the 2D interface, the 3D interface has proven to be surprisingly usable, and the 3D drawings sometimes provide insights that are not so obvious in the 2D drawings.

This paper describes an online animated graph drawing method. The method deals with huge graphs which are partially unknown. It is instantiated in OFDAV, a web diagram visualizer.

Grappa is an extensible graph drawing package written in Java. The package comprises classes that implement graph representation, presentation and layout services. It provides an application programming interface (API) on top of which Web-based applications that need to visualize information in terms of graphs, such as process flows, business workflows or program dependencies, can be built. Through subclassing, the classes that implement an application inherit graph drawing and layout services provided by Grappa, these services can be enhanced and customized for the specific application. To illustrate its utility, a new version of Improvise, a multimedia process modeling environment, was written on top of Grappa.

GraVis is a powerful, interactive graph visualization system, designed to be generally usable in research and practical applications. The implementation of GRAVis is based on a flexible object-oriented system architecture, portable to many platforms. The intuitive and efficient user interface is completed by the ability of the base system to meet the requirements of future applications.

The touching graph of balls is a graph that admits a representation by non-intersecting balls in the space (of prescribed dimension), so that its edges correspond to touching pairs of balls. By a classical result of Koebe [5], the disc touching graphs are exactly the planar graphs. This paper deals with a recognition of unit-ball touching graphs. The 2-dimensional case was proved to be NP-hard by Breu and Kirkpatrick [1]. We show in this paper that also unit-ball touching graphs in dimensions 3 and 4 are NP-hard to recognize. By a recent result of Kirkpatrick and Rote, these results may be transferred in ball-touching graphs in one dimension higher.

Known realizations of geometric representations of graphs, like contact, intersection, etc., are “continuous”, in the sense that the geometric objects are drawn in Euclidean space with real numbers as coordinates. In this paper, we initiate the study of dicrete versions of contact and intersection graphs and examine their relation to their continuous counterparts. The classes of graphs arising appear to have interesting properties and are thus interesting in their own right. We also study realizability, characterizations as well as intractability questions for the resulting new classes of graphs.

We study the area requirement of h-v drawings of complete binary trees. An h-v drawing of a binary tree t is a drawing of t such that (a) nodes are points with integer coordinates, (b) each edge is either a rightward-horizontal or a downward-vertical straight-line segment from a node to one of its children, (c) edges do not intersect, and (d) if t₁ and t₂ are immediate subtrees of a node u, the enclosing rectangles of the drawings of t₁ and t₂ are disjoint. We prove that, for any complete binary tree t of height h ≥ 3 and with n nodes, the area of the optimum h-v drawing of t is equal to (a) 2.5n − 4.5 $$\sqrt {(n + 1)/2} $$ + 3.5 if h is odd, (b) 2.5n − 3.25 $$\sqrt {n + 1} $$ + 3.5 otherwise. As far as we know, this is one of the few examples in which a closed formula for the minimum-area drawing of a graph has been explicitly found. Furthermore this minimum-area h-v drawing can be constructed in linear time. As a consequence of this result and the result of Trevisan (1996), we have that h-v drawings are provably less area-efficient than strictly upward drawings when we restrict ourselves to complete binary trees. We also give analogous results for the minimum-perimeter and the minimum-enclosing square area h-v drawings.

The main problem considered in this paper is the following: given two trees both with n vertices, whether it is possible to draw them on the plane with the same set of vertices without crossings and duplicated edges. We formulate this problem in terms of packing graphs and give a solution in several situations. We also solve some related problems on drawing trees and cycles.

In this paper, we study orthogonal graph drawings from a practical point of view. Most previously existing algorithms restricted the attention to graphs of maximum degree four. Here we study orthogonal drawing algorithms that work for any input graph, and discuss different models for such drawings. Then we introduce the three-phase method, a generic technique to create high-degree orthogonal drawings. This approach simplifies the description and implementation of orthogonal graph drawing, and can be applied to global as well as interactive and incremental settings.

The difference between displaying networks with 100–1000 nodes and displaying ones with 10,000–100,000 nodes is not merely quantitative, it is qualitative. Layout algorithms suitable for the former are too slow for the latter, requiring new algorithms or modified (often relaxed) versions of existing algorithms to be invented. The density of nodes and edges displayed per inch of screen real estate requires special visual techniques to filter the graphs and focus attention. A system for investigating and exploring such large, complex data sets needs to be able to display both graph structure and node and edge attributes so that patterns and information hidden in the data can be seen. We describe a tool that addresses these needs, the NicheWorks tool. We describe and comment on the available layout algorithms and the linked views system, and detail an example of the use of NicheWorks for analyzing web sites.

The automatic layout of software diagrams is a very attractive graph drawing application for use in software tools. Object-oriented software may be modelled using a visual language called the Unified Modeling Language (UML). In this paper we present an algorithm for the automatic layout of UML class diagrams using an extension of the Sugiyama algorithm together with orthogonal drawing. These diagrams visualize the static structure of object-oriented software systems and are characterised by the use of two main types of edges corresponding to different relationships between the classes. The graph drawing algorithm accounts for these concepts by treating the different edge types in different ways.

This paper introduces the LINK system as a flexible tool for the creation, manipulation, and drawing of graphs and hypergraphs. We describe the basic architecture of the system and illustrate its flexibility with several examples. LINK is distinguished from existing software for discrete mathematics by its layered interface, including a graphical user interface tied into an object-oriented Scheme language interface with access to Tk, and an extensible underlying set of C++ libraries. We conclude by briefly discussing roles LINK has played in research and education.

This report describes the Fourth Annual Graph Drawing Contest, held in conjunction with the 1997 Graph Drawing Symposium in Rome, Italy. The purpose of the contest is to monitor and challenge the current state of the art in graph-drawing technology [2, 3, 4].