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 complete binary trees inside rectilinear polygons

Most of graph drawing algorithms draw graphs on unbounded planes. However, there are applications that require graphs to be drawn on the plane inside a given polygon. In this paper, a new algorithm for planar orthogonal drawing of complete binary trees inside rectilinear polygons is presented. Uniform distribution of nodes of graphs on drawing regions is one of the aesthetics criteria in graph drawing. The goal of this paper is to produce planar orthogonal drawings with a relatively uniform node distribution and few edge bends. The proposed algorithm can be considered as a generalization of the H-tree layout method for rectilinear polygons. A new linear time algorithm is also given for bisecting rectilinear polygons into two equi-area rectilinear sub-polygons.     

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.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical 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 and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. 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 linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

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.     

A browser for directed graphs

A general-purpose browser for directed graphs is described. The browser provides operations to examine and edit graphs and to generate a layout for a graph automatically that minimizes edge crossings. Two layout algorithms were implemented. A hierarchical graph layout algorithm was found to be best for directed graphs. The graph browser also has facilities that allow it to be integrated with other applications (e.g. a program browser). These facilities and our experiences building a program call-graph browser are described.     

QUAD: a computer package for the analysis of QUantal assay data

The computer package QUAD has been developed at the University of Kent, U.K. It is menu-driven and written in Advanced BASIC. It runs on IBM PC compatible machines equiped with a suitable graphics facility such as CGA or simulated CGA. QUAD is available on a floppy disk, for a small handling charge.

QUAD has four main functions: it performs a logit analysis of quantal assay data; it provides a flexible way of analysing the data, allowing dose transformations and providing alternative confidence intervals for ED_p values; it produces a range diagnostics for assessing the fit of models to data; it provides and fits two families of extended models, each containing the logit as a special case.

The package makes use of the latest statistical research, and fitted models are displayed by means of the good graphics facilities available on microcomputers.

This document describes the facilities available in detail, and provides and discusses illustrations of the package at work. QUAD has been designed as a pilot package. Further additions and developments are planned and described later.     

A graph-theoretic language extension for an interactive computer graphics environment

A programming language extension, AGILE, for the processing of graphs within an interactive computer graphics environment, is defined. The language is intended to be used for expressing and illustrating graph-theoretic algorithms and applications. However it does not deal with the actual drawing or display of graphs; rather one is able to access an existing general-purpose graphics package. The language then is intended to be used, in conjunction with a graphics package, as a tool for the production of more specialised graphics systems: the language allows one to naturally exploit the underlying graph structure found in a wide class of problems, while a graphics environment permits the elegant display of (and interaction with) such representations.AGILE extends the host language, C, by the addition of a graph database, and operators and control structures to manipulate this database. The graph structure is composed of five basic types: nodes, edges, graphs, sets and bugs (references). A general set of operators and tests are provided, including those for entity creation and deletion, node and edge traversal and tests for equality and containment of sets and graphs. Edges may be treated as being either directed or undirected; also multiple edges between nodes and self-loops are allowed. Arbitrary values and properties may be associated with each of the basic types. In particular, since a node may have a graph as value, a graph hierarchy is possible. Graphics primitives are provided by the GPAC graphics system.Three substantial applications have been programmed in the language: a system for producing diagrams of graphs and a class of data structures, a system for animating four algorithms for finding the maximum flow in a network, and a system for animating and making films of systems dynamics models.Several examples of programmes written in AGILE are included.     

A display package for CAD of control systems

A multi-access computer system has been installed at the Control Systems Centre of the University of Manchester Institute of Science and Technology. The application of this computer to research into the computer aided design of industrial control systems involved the connection of two keyboard display terminals to the system. The ARDS storage tube displays chosen had the advantages of being teletypewriter compatible and not requiring the connection of a satellite computer A graphics package for the entry and structuring of data derived from the stability analysis of control systems was required as soon as possible after the installation was commissioned. The initial package enabled data to be entered by program and then selected and plotted by keyboard requests. Translation, scaling, alteration of the method of plotting (with points or vectors) and the selection of different items for the display were all carried out by keyboard interaction For long term CAD work a more extensive graphics package was required, the specification was determined following feedback from users of the initial package. It provided additional facilities for graphic interaction, alphanumeric annotation of the displays, specialized drawing and data entry functions and the storing of any pictures built up by the user, as well as a more linked data structure. The structure and facilities of this package are described.     

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.