Minimising the Number of Bends and Volume in 3-Dimensional Orthogonal Graph Drawings with a Diagonal Vertex Layout

A 3-dimensional orthogonal drawing of a graph with maximum degree at most 6, positions the vertices at grid-points in the 3-dimensional orthogonal grid, and routes edges along grid-lines such that edge routes only intersect at common end-vertices. Minimising the number of bends and the volume of 3-dimensional orthogonal drawings are established criteria for measuring the aesthetic quality of a given drawing. In this paper we present two algorithms for producing 3-dimensional orthogonal graph drawings with the vertices positioned along the main diagonal of a cube, so-called diagonal drawings. This vertex-layout strategy was introduced in the 3-BENDS algorithm of Eades et al. [Discrete Applied Math. 103:55–87, 2000]. We show that minimising the number of bends in a diagonal drawing of a given graph is NP-hard. Our first algorithm minimises the total number of bends for a fixed ordering of the vertices along the diagonal in linear time. Using two heuristics for determining this vertex-ordering we obtain upper bounds on the number of bends. Our second algorithm, which is a variation of the above-mentioned 3-BENDS algorithm, produces 3-bend drawings with n³+o(n³) volume, which is the best known upper bound for the volume of 3-dimensional orthogonal graph drawings with at most three bends per edge.     

Three-Dimensional Orthogonal Graph Drawing with Optimal Volume

An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid that only possibly intersect at common endpoints. In this paper we study three-dimensional orthogonal drawings and provide lower bounds for three scenarios: (1) drawings where the vertices have a bounded aspect ratio, (2) drawings where the surfaces of vertices are proportional to their degrees, and (3) drawings without any such restrictions. Then we show that these lower bounds are asymptotically optimal, by providing constructions that in all scenarios match the lower bounds within a constant factor.     

Kronecker product graph matching

In this paper the Interpolator-based Kronecker product graph matching (IBKPGM) algorithm for performing attributed graph matching is presented. The IBKPGM algorithm is based on the Kronecker product graph matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of graph matching problems based on attributed graphs, allowing the structure of the graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input graphs as well as between all edges of the reference and input graphs are avoided.     

Greedy rankings and arank numbers

A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices of the same rank contains a vertex of strictly larger rank. A ranking is locally minimal if reducing the rank of any single vertex produces a non-ranking. A ranking is globally minimal if reducing the ranks of any set of vertices produces a non-ranking. A ranking is greedy if, for some ordering of the vertices, it is the ranking produced by assigning ranks in that order, always selecting the smallest possible rank. We will show that these three notions are equivalent. If a ranking satisfies one property it satisfies all three. As a consequence of this and known results on arank numbers of paths we improve known upper bounds for on-line ranking of paths and cycles.     

Finding and counting given length cycles

We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results. This work was supported in part by The Basic Research Foundation administrated by The Israel Academy of Sciences and Humanities.     

Two models of two-dimensional bandwidth problems

The two-dimensional bandwidth problem is to embed a graph G into an n×n grid in the plane such that the maximum distance between adjacent vertices is as small as possible. Here, the “distance” has two different meanings: the L₁-norm distance and L_∞-norm distance. So we have two models of two-dimensional bandwidth problem. This paper investigates the basic properties and relations of these two models. Some lower bounds, upper bounds, and exact results are presented.     

A Visualization Framework and User Studies for Overloaded Orthogonal Drawings

Overloaded orthogonal drawing (OOD) is a recent graph visualization style specifically conceived for directed graphs. It merges the advantages of some popular drawing conventions like layered drawings and orthogonal drawings, and provides additional support for some common analysis tasks. We present a visualization framework called DAGView, which implements algorithms and graphical features for the OOD style. Besides the algorithm for acyclic digraphs, the DAGView framework implements extensions to visualize both digraphs with cycles and undirected graphs, with the additional possibility of taking into account user preferences and constraints. It also supports an interactive visualization of clustered digraphs, based on the use of strongly connected components. Moreover, we describe an experimental user study, aimed to investigate the usability of OOD within the DAGView framework. The results of our study suggest that OOD can be effectively exploited to perform some basic tasks of analysis in a faster and more accurate way when compared to other drawing styles for directed graphs.     

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

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

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

Mental map preserving graph drawing using simulated annealing

Visualizing graphs has been studied extensively in the community of graph drawing and information visualization over the years. In some applications, the user is required to interact with a graph by making slight changes to the underlying graph structure. To visualize graphs in such an interactive environment, it is desirable that the differences between the displays of the original and the modified graphs be kept minimal, allowing the user to comprehend the changes in the graph structure faster. As the mental map concept refers to the presentation of a person’s mind while exploring visual information, the better the mental map is preserved, the easier the structure change of a graph is understood. It is somewhat surprising that preserving the user’s mental map has largely been ignored in the graph drawing community in the past. We propose an effective mental-map-preserving graph drawing algorithm for straight-line drawings of general undirected graphs based on the simulated-annealing technique. Our experimental results and questionnaire analysis suggest this new approach to be promising.     

Drawing graphs with right angle crossings

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

Three-dimensional graph drawing

Graph drawing research has been mostly oriented toward two-dimensional drawings. This paper describes an investigation of fundamental aspects of three-dimensional graph drawing. In particular we give three results concerning the space required for three-dimensional drawings. We show how to produce a grid drawing of an arbitraryn-vertex graph with all vertices located at integer grid points, in ann×2n×2n grid, such that no pair of edges cross. This grid size is optimal to within a constant. We also show how to convert an orthogonal two-dimensional drawing in anH×V integer grid to a three-dimensional drawing with volume. Using this technique we show, for example, that three-dimensional drawings of binary trees can be computed with volume . We give an algorithm for producing drawings of rooted trees in which thez-coordinate of a node represents the depth of the node in the tree; our algorithm minimizes thefootprint of the drawing, that is, the size of the projection in thexy plane. Finally, we list significant unsolved problems in algorithms for three-dimensional graph drawing. This work was performed as part of the Information Visualization Group(IVG) at the University of Newcastle. The IVG is supported in part by IBM Toronto Laboratory.     

Exact bounds for robust stability of output feedback controlled fractional‐order systems with single parameter perturbations

This article investigates exact robust stability bounds of output feedback controlled fractional‐order systems with the commensurate order and single parameter perturbations in all system coefficient matrices. First, a sufficient and necessary condition for robust asymptotical stability of such systems is obtained by using the Kronecker product. Then the maximal upper bounds and minimum lower bounds for robust asymptotical stability are established, respectively, without conservatism by transforming such problems into checking whether the matrix with single parameter perturbations is nonsingular or not. Finally, two numerical examples are given to show the effectiveness of the proposed results.     

Level-2 condition numbers for least-squares solution of Kronecker product linear systems

Kronecker product linear systems arise more and more often in the real world. In this paper, we consider the minimum norm least-squares solution of Kronecker product linear systems (A? B)x=b by extending some known results from nonsingular cases to singular or rectangular cases. We investigate the level-2 condition numbers, and the corresponding bounds of these condition numbers.     

Drawing Trees Symmetrically in Three Dimensions

Abstract. Symmetric graph drawing enables a clear understanding of the structure of the graph. Previous work on symmetric graph drawing has focused on two dimensions. Symmetry in three dimensions is much richer than that of two dimensions. This is the first paper to extend symmetric graph drawing into three dimensions. More specifically, the paper investigates the problem of drawing trees symmetrically in three dimensions. First, we suggest a model for drawing trees symmetrically in three dimensions. Based on this model, we present a linear time algorithm for finding the maximum number of three-dimensional symmetries in trees. We also present a three-dimensional symmetric drawing algorithm for trees.     

Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.     

Efficient Orthogonal Drawings of High Degree Graphs

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

Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a planar drawing of G. Finding planar automorphisms is the first and most difficult step in constructing planar symmetric drawings of graphs. The problem of determining whether a given graph has a nontrivial geometric automorphism is NP-complete for general graphs. The two previous papers in this series have discussed the problem of drawing planar graphs with a maximum number of symmetries, for the restricted cases where the graph is triconnected and biconnected. This paper extends the previous results to cover planar graphs that are oneconnected. We present a linear time algorithm for drawing oneconnected planar graphs with a maximum number of symmetries.     

A note on boundingk-terminal reliability

A generalization of a theorem of Lomonosov and Polesskii is proved, which provides a novel method for determining upper bounds on the probability that a graph contains a Steiner tree (k-terminal reliability).This research was supported by NSERC Canada under Grant No. A0579.