Parametric graph drawing

A diagram is a drawing on the plane that represents a graph like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams     

Using graph parsing for automatic graph drawing

This paper presents a procedure for automatically drawing directed graphs. Our system, Clan-based Graph Drawing Tool (CG), uses a unique clan-based graph decomposition to determine intrinsic substructures (clans) in the graph and to produce a parse tree. The tree is given attributes that specify the node layout. CG then uses tree properties with the addition of “routing nodes” to route the edges. The objective of the system is to provide, automatically, an aesthetically pleasing visual layout for arbitrary directed graphs. The prototype has shown the strengths of this approach. The innovative strategy of clan-based graph decomposition is the first digraph drawing technique to analyze locality in the graph in two dimensions. The typical approach to drawing digraphs uses a single dimension, level, to arrange the nodes     

Rapid graph layout using space filling curves

Network data frequently arises in a wide variety of fields, and node-link diagrams are a very natural and intuitive represen- tation of such data. In order for a node-link diagram to be effective, the nodes must be arranged well on the screen. While many graph layout algorithms exist for this purpose, they often have limitations such as high computational complexity or node colocation. This paper proposes a new approach to graph layout through the use of space filling curves which is very fast and guarantees that there will be no nodes that are colocated. The resulting layout is also aesthetic and satisfies several criteria for graph layout effectiveness.     

A stable graph layout algorithm for processes

Process mining enables organizations to analyze data about their (business) processes. Visualization is key to gaining insight into these processes and the associated data. Process visualization requires a high‐quality graph layout that intuitively represents the semantics of the process. Process analysis additionally requires interactive filtering to explore the process data and process graph. The ideal process visualization therefore provides a high‐quality, intuitive layout and preserves the mental map of the user during the visual exploration. The current industry standard used for process visualization does not satisfy either of these requirements. In this paper, we propose a novel layout algorithm for processes based on the Sugiyama framework. Our approach consists of novel ranking and order constraint algorithms and a novel crossing minimization algorithm. These algorithms make use of the process data to compute stable, high‐quality layouts. In addition, we use phased animation to further improve mental map preservation. Quantitative and qualitative evaluations show that our approach computes layouts of higher quality and preserves the mental map better than the industry standard. Additionally, our approach is substantially faster, especially for graphs with more than 250 edges.     

A graph grammar programming style for recognition of music notation

Graph grammars are a promising tool for solving picture processing problems. However, the application of graph grammars to diagram recognition has been limited to rather simple analysis of local symbol configurations. This paper introduces the Build-Weed-Incorporate programming style for graph grammars and shows its application in determining the meaning of complex diagrams, where the interaction among physically distant symbols is semantically important. Diagram recognition can be divided into two stages: symbol recognition and high-level recognition. Symbol recognition has been studied extensively in the literature. In this work we assume the existence of a symbol recognizer and use a graph grammar to assemble the diagram's information content from the symbols and their spatial relationships. The Build-Weed-Incorporate approach is demonstrated by a detailed discussion of a graph grammar for high-level recognition of music notation. See Appendix A for an illustration of the terms for musical symbols used in this paper.     

A class of linearly parsable graph grammars

Summary Specializing an existing graph grammar model we look in detail at node context-free graph grammars. With a slight generalization the parse trees for context-free Chomsky grammars can be used to describe derivations of these graph grammars.As shown already in former works the precedence graph grammars are defined as a subclass of context-free graph grammars by certain algebraic restrictions on the form of the rules. Then we can prove that every precedence grammar is unambiguous and additionally the reduction process in such a grammar read as replacement system is finite.The most important aim in defining the predence relations was a simple parsing method. This is realized because it is shown that the syntactic analysis for precedence graph grammars can be done in a time which linearly depends on the size of the input graph.The whole method has been implemented and a documentation is available.     

新型属性图文法反应式规约验证方法

属性图文法广泛应用在软件设计阶段建模和分析阶段。命题式时序逻辑（propositional temporal logic）无法直接表达建模实体包含随时间演化的关联属性反应式规约,提出一种可支持通用图文法转换系统中相应规约的验证方法,通过引入标记节点及属性,将包含相应关联属性的规约公式等价转换为命题式时序逻辑,从而可以间接支持该类型规约的验证。以流行的对象式属性图文法模型检测工具GROOVE为平台,结合启发案例,验证了所提出方法的有效性。     

Logichart — Intelligible Program Diagram for Prolog and its Processing System

An intelligible program diagram called Logichart has been developed for Prolog visualization. Its syntax rules and layout rules are formalized in terms of an attribute graph grammar. This grammar is underlain by a context–free graph grammar whose productions are defined to formalize the graph–syntax rules of Logichart diagrams. Semantic rules attached to the productions are defined in such a way that they can extract the layout information needed to display a Logichart diagram as attributes. Our Prolog visualization system, which has been implemented based on the attribute graph grammar, can draw a Logichart diagram for any correct Prolog program (completeness), and any Logichart diagram displayed by the system is always valid for the grammar (soundness). The system can also display the execution of a Prolog program in real time; that is, the Logichart diagram is dynamically updated as the program runs.     

Computing with graphs and graph transformations

Many software applications require the construction and manipulation of graphs. In standard programming languages, this is accomplished using low‐level mechanisms such as pointer manipulation or array indexing. In contrast, graph productions are a convenient high‐level visual notation for coding graph modifications. A graph production replaces one subgraph by another subgraph. Graph productions can define a graph grammar and graph language, or can directly transform an input graph into an output graph. Graph transformation has been applied in many areas, including the definition of visual languages and their tools, the construction of software development environments, the definition of constraint programming algorithms, the modeling of distributed systems, and the construction of neural networks. One application is presented in detail: the interpretation of mathematical notation in scanned document images. The graph models the set of mathematical symbols, and their spatial and logical relationships. This graph is transformed by productions written in the PROGRES language. Copyright © 1999 John Wiley & Sons, Ltd.     

Specifying behavioral semantics of UML diagrams through graph transformations

The Unified Modeling Language (UML) has been widely accepted as a standard for modeling software systems from various perspectives. The intuitive notations of UML diagrams greatly improve the communication among developers. However, the lack of a formal semantics makes it difficult to automate analysis and verification. This paper offers a graphical yet formal approach to specifying the behavioral semantics of statechart diagrams using graph transformation techniques. It supports many advanced features of statecharts, such as composite states, firing priority, history, junction, and choice. In our approach, a graph grammar is derived automatically from a state machine to summarize the hierarchy of states. Based on the graph grammar, the execution of a set of non-conflict state transitions is interpreted by a sequence of graph transformations. This facilitates verifying a design model against system requirements. To demonstrate our approach, we present a case study on a toll-gate system.     

EGG图文法语法分析算法的研究

EGG是一种基于边的上下文相关图文法形式化框架,其语法分析(归约操作)算法是该文法重要的组成部分。在简要介绍EGG的基础上,给出了EGG语法分析算法的设计,其中包括子图匹配算法、子图替换算法和算法计算复杂性的分析。为了展示如何用EGG来定义图语言,特别是如何用所设计的归约算法来分析图,文中以程序流程图为例,给出了相关的EGG形式定义以及对一个具体流程图的归约过程,并探讨了可能降低分析算法复杂性的一些途径。     

The Grasper-CL graph management system

Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in COMMON LISP and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL graphs can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL employs a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.     

Library layout via graph theory

This article reports on a case study of the design of the new Law library at the University of Canterbury in New Zealand. The objective was to produce a layout which attempts to minimize expected travel and is convenient for all users, including librarians. The problem differed from most layout studies in two ways. There are three identifiable groups of users of the library: the librarians, the students, and the law professors. Also, the intensity of travel between facilities in the library is location dependent. None of the existing layout methods that the authors tried seemed capable of producing a suitable layout. Using graph theory, the authors developed and implemented a flexible layout approach which led to a successful design. This article summarizes the steps involved, including obtaining a compromise layout which satisfied the needs of the three groups of users.     

Trash removal algorithm for fast construction of the elliptic Gabriel graph using Delaunay triangulation

Given a set of points P, finding near neighbors among the points is an important problem in many applications in CAD/CAM, computer graphics, computational geometry, etc. In this paper, we propose an efficient algorithm for constructing the elliptic Gabriel graph (EGG), which is a generalization of the well-known Gabriel graph and parameterized by a non-negative value α. Our algorithm is based on the observation that a candidate point which may define an edge of an EGG with a given point p∈P is always in the scaled Voronoi region of p with a scale factor 2/α² when the parameter α<1. From this observation, we can reduce the search space for locating neighbors of p in the EGG. For the case of α≥1, due to the fact that EGG is a subgraph of the Delaunay graph of P, EGG can be efficiently computed by watching the validity of each edge in the Delaunay graph. The proposed algorithm is shown to have its time complexity as O(n³) in the worst case and O(n) in the average case when α is moderately close to unity. The idea presented in this paper may similarly apply to other problems for the proximity search for point sets.     

Coherent time-varying graph drawing with multifocus+context interaction

We present a new approach for time-varying graph drawing that achieves both spatiotemporal coherence and multifocus+context visualization in a single framework. Our approach utilizes existing graph layout algorithms to produce the initial graph layout, and formulates the problem of generating coherent time-varying graph visualization with the focus+context capability as a specially tailored deformation optimization problem. We adopt the concept of the super graph to maintain spatiotemporal coherence and further balance the needs for aesthetic quality and dynamic stability when interacting with time-varying graphs through focus+context visualization. Our method is particularly useful for multifocus+context visualization of time-varying graphs where we can preserve the mental map by preventing nodes in the focus from undergoing abrupt changes in size and location in the time sequence. Experiments demonstrate that our method strikes a good balance between maintaining spatiotemporal coherence and accentuating visual foci, thus providing a more engaging viewing experience for the users.     

Elliptic Gabriel graph for finding neighbors in a point set and its application to normal vector estimation

Point-based shape representation has received increased attention in recent years, mainly due to its simplicity. One of the most fundamental operations for point set processing is to find the neighbors of each point. Mesh structures and neighborhood graphs are commonly used for this purpose. However, though meshes are very popular in the field of computer graphics, neighbor relations encoded in a mesh are often distorted. Likewise, neighborhood graphs, such as the minimum spanning tree (MST), relative neighborhood graph (RNG), and Gabriel graph (GG), are also imperfect as they usually give too few neighbors for a given point. In this paper, we introduce a generalization of Gabriel graph, named elliptic Gabriel graph (EGG), which takes an elliptic influence region instead of the circular region in GG. In order to determine the appropriate aspect ratio of the elliptic influence region of EGG, this paper also presents the analysis between the aspect ratio of the elliptic influence region and the average valence of the resulting neighborhood. Analytic and empirical test results are included.     

A graph theory-based approach to route location in railway interlocking

The location and verification of routes is an important component of railway interlocking logic design. The interlocking routes are typically listed manually by experienced signaling engineers, and this task is both time consuming and expensive. In this paper, an automatic, graph theory-based approach to route location and verification is presented. In this new approach, a component-based model is used to represent the topology of the station layout, and a modified matrix algorithm based on graph theory is used to locate all of the routes in a given station. This algorithm exhibits superior performance in the location and verification of routes and is universally applicable, irrespective of the station layout. When a station is modified, the designers can simply update the topological data for the station, and the new route information can be obtained automatically.     

Graph expressions and graph rewritings

We define an algebraic structure for the set of finite graphs, a notion of graph expression for defining them, and a complete set of equational rules for manipulating graph expressions. (By agraph we mean an oriented hypergraph, the hyperedges of which are labeled with symbols from a fixed finite ranked alphabet and that is equipped with a finite sequence of distinguished vertices). The notion of a context-free graph grammar is introduced (based on the substitution of a graph for a hyperedge in a graph). The notion of an equational set of graphs follows in a standard way from the algebraic structure. As in the case of context-free languages, a set of graphs is contextfree iff it is equational. By working at the level of expressions, we derive from the algebraic formalism a notion of graph rewriting which is as powerful as the usual one (based on a categorical approach) introduced by Ehrig, Pfender, and Schneider.This work has been supported by the PRC Mathématiques et Informatique. Reprints can be requested from B. Courcelle by electronic mail at the following address (UUCP network): mcvax!inria!geocub!courcell.     

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.     

Hierarchical graph visualization using neural networks.

An algorithm based on a Hopfield network for solving the hierarchical graph visualization problem is presented. It simultaneously minimizes the number of crossings and total path length to produce two-dimensional drawings easily interpreted by human observers. Traditional heuristics often follow a more local optimization approach where "readability" criteria are sequentially applied, such as applying the barycentric heuristic followed by the priority layout heuristic. As a result of the more global approach, the neural network achieved comparable crossing minimization to the barycentric heuristic while simultaneously reducing total path length up to 50% over the priority layout heuristic for the benchmarks tested.