Drawing slicing graphs with face areas

We consider orthogonal drawings of a plane graph G$G$ with specified face areas. For a natural number k$k$, a k$k$-gonal drawing of G$G$ is an orthogonal drawing such that the boundary of G$G$ is drawn as a rectangle and each inner face is drawn as a polygon with at most k$k$ corners whose area is equal to the specified value. In this paper, we show that every slicing graph G$G$ with a slicing tree T$T$ and a set of specified face areas admits a 10-gonal drawing D$D$ such that the boundary of each slicing subgraph that appears in T$T$ is also drawn as a polygon with at most 10 corners. Such a drawing D$D$ can be found in linear time.     

Drawing layered graphs with port constraints

Complex software systems are often modeled using data flow diagrams, in which nodes are connected to each other through dedicated connection points called ports. The influence a layout algorithm has on the placement of ports is determined by port constraints defined on the corresponding node.In this paper we present approaches for integrating port constraints into the layer-based approach to graph drawing pioneered by Sugiyama et al. We show how our layout algorithm, called KLay Layered, progresses from relaxed to more restricted port constraint levels as it executes, and how established algorithms for crossing minimization and edge routing can be extended to support port constraints. Compared to the previous layout algorithms supporting ports, our algorithm produces fewer edge crossings and bends and yields pleasing results.We also explain and evaluate how layout algorithms can be kept simple by using the concept of intermediate processors to structure them in a modular way. A case study integrating our layout algorithm into UC Berkeley's Ptolemy tool illustrates how KLay Layered can be integrated into Java-based applications.     

Drawing graphs by eigenvectors: theory and practice

The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Two important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper, we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space.     

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.     

Width-restricted layering of acyclic digraphs with consideration of dummy nodes

This paper deals with the problem of finding graph layerings restricted to a given maximal width. However, other than previous approaches for width-restricted layering, we take into account the space for dummy nodes, which are introduced by edges crossing a layer. The main result is that the problem of finding a width-restricted layering under consideration of dummy nodes is NP-complete even when all regular nodes have the same constant width and all dummy nodes have the same constant width.     

A Near-Linear Area Bound for Drawing Binary Trees

Abstract. We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n -node binary tree. In particular, it is shown that O(n ^1+ɛ ) area is always sufficient for an arbitrary constant ɛ>0 .     

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.     

Evaluating esthetics for user-sketched layouts of clustered graphs with known clustering information

This paper aims to empirically analyze the esthetics for user-sketched layouts of clustered graphs with known clustering information. In our experiments, given not only the adjacency list of a clustered graph but also its predefined clustering information, each participant was asked to manually sketch clustered graphs “nicely” from scratch on a tablet system using a stylus. Different from previous works, the main concern in this paper is on which graph drawing esthetics people favor when sketching their own drawings of clustered graphs with known clustering information. Another concern of this paper is on the esthetics of clustered graph layouts employed by participants which include not only characteristics and structures of the final graph layouts but also the behavior of user's sketching process (including layout creation and adjustment). By observing all layouts and drawing processes, the drawing strategies which participants applied and the drawing esthetics are analyzed. Results show that most participants were unsurprisingly able to draw graphs with clear presence of bridge edges and clustering cohesiveness; more importantly, to distinguish clusters within the restricted-size tablet screen during the drawing process, some of the participants were still able to make each cluster with fewer edge crossings, more symmetries, and more alignment of grid in a smaller drawing area where the cluster spreads. Our results support that to alleviate user's complex drawing tasks, aside from the grid-based editing function suggested by the previous work, graph drawing systems should also provide the clustering information if the structure of the graph to be drawn is known.     

MWTmat—application of multiscale wavelet tomography on potential fields

Wavelet analysis is a well-known technique in the sciences to extract essential information from measured signals. Based on the theory developed by previous studies on the Poisson kernel family, this study presents an open source code, which allows for the determination of the depth of the source responsible for the measured potential field. MWTmat, based on the Matlab platform, does not require the wavelet tool box, is easy to use, and allows the user to select the analyzing wavelets and parameters. The program offers a panel of 10 different wavelets based on the Poisson kernel family and the choice between a fully manual and a semiautomatic mode for selection of lines of extrema. The general equations for both horizontal and vertical derivative wavelets are presented in this study, allowing the user to add new wavelets. Continuous wavelet analyses can be used to efficiently analyze electrical, magnetic, and gravity signals; examples are presented here. The MWTmat code and the multiscale wavelet tomography approach are an efficient method for investigating spatial and temporal changes of sources generating potential field signals.     

Geometric characterization and clustering of graphs using heat kernel embeddings

In this paper, we investigate the use of heat kernels as a means of embedding the individual nodes of a graph in a vector space. The reason for turning to the heat kernel is that it encapsulates information concerning the distribution of path lengths and hence node affinities on the graph. The heat kernel of the graph is found by exponentiating the Laplacian eigensystem over time. In this paper, we explore how graphs can be characterized in a geometric manner using embeddings into a vector space obtained from the heat kernel. We explore two different embedding strategies. The first of these is a direct method in which the matrix of embedding co-ordinates is obtained by performing a Young–Householder decomposition on the heat kernel. The second method is indirect and involves performing a low-distortion embedding by applying multidimensional scaling to the geodesic distances between nodes. We show how the required geodesic distances can be computed using parametrix expansion of the heat kernel. Once the nodes of the graph are embedded using one of the two alternative methods, we can characterize them in a geometric manner using the distribution of the node co-ordinates. We investigate several alternative methods of characterization, including spatial moments for the embedded points, the Laplacian spectrum for the Euclidean distance matrix and scalar curvatures computed from the difference in geodesic and Euclidean distances. We experiment with the resulting algorithms on the COIL database.     

Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields

This paper presents a reactive scheduling approach for flexible manufacturing systems, which integrates the overall energy consumption of the production. This work is justified by the growing needs of manufacturers for energy-aware control, due to new important environmental criteria, which holds true in the context of high reactivity. It makes production hard to predict. The proposed reactive scheduling model is based on potential fields. In this model, resources that sense the intentions from products are able to switch to standby mode to avoid useless energy consumption and emit fields to attract products. Simulations are provided, featuring three indicators: makespan, overall energy consumption and the number of resource switches. Real experiments were carried out to illustrate the feasibility of the approach on a real system and validate the simulation results.     

An Algorithm for Straight-Line Drawing of Planar Graphs

We present a new algorithm for drawing planar graphs on the plane. It can be viewed as a generalization of the algorithm of Chrobak and Payne, which, in turn, is based on an algorithm by de Fraysseix, Pach, and Pollack. Our algorithm improves the previous ones in that it does not require a preliminary triangulation step; triangulation proves problematic in drawing graphs ``nicely,' as it has the tendency to ruin the structure of the input graph. The new algorithm retains the positive features of the previous algorithms: it embeds a biconnected graph of n vertices on a grid of size (2n-4) x (n-2) in linear time. We have implemented the algorithm as part of a software system for drawing graphs nicely. Received September 21, 1995; revised March 15, 1996.     

Drawing directed graphs using quadratic programming

We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes.     

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.     

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.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.     

A layout algorithm for undirected compound graphs

We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions.     

Avoiding local minima in the potential field method using input-to-state stability

Supported by a novel field definition and recent control theory results, a new method to avoid local minima is proposed. It is formally shown that the system has an attracting equilibrium at the target point, repelling equilibriums in the obstacle centers and saddle points on the borders. Those unstable equilibriums are avoided capitalizing on the established Input-to-State Stability (ISS) property of this multistable system. The proposed modification of the PF method is shown to be effective by simulation for a two variable integrator and then applied to a unicycle-like wheeled mobile robots which is subject to additive input disturbances.     

Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks.     

Drawing planar graphs using the canonical ordering

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:

Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n?4)×(n?2) grid, wheren is the number of vertices.

Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.

Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.

Every triconnected planar graphG admits a planar polyline grid drawing on a (2n?6)×(3n?9) grid with minimum angle larger than 2/d radians and at most 5n?15 bends, withd the maximum degree.

These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.