Graph Parsing Techniques for Visualizing Directed Graphs

C. L. McCreary and Fwu-Shan Shieh
Department of Computer Science and Engineering
Auburn University

1. Background

The goal of the proposed work is to develop techniques for visualizing directed graphs. Our preliminary work uses a two step process that first analyzes the graph through parsing it and then applies attributes to the parse tree to determine the node and edge layout. Our experimentation has convinced us that the technique is superior to others currently in practice.

Many researchers have studied this problem and many graph drawing systems have been developed (see 10. for a complete list). The aesthetic criteria of the systems vary. The objectives may include requirements of uniform edge length, minimum number of edge crossings, straight edges, grid drawings (edges are either horizontal or vertical), minimal bends in the edges, minimum area covered, and display of symmetries. Some limit the input to a graphs with particular propeties, (planar graphs, trees, and graphs with maximum degree of four), or to graphs taht are intended for specific applications (Petri nets, network representations, digital system schematic diagrams, PERT diagrams or flowcharts). We are developing CG (Clan-based Graph Drawing Tool) to convert a textual description of an arbitrary directed graph to a visual representation. The objective of the system is to provide an aesthetically pleasing visual layout for arbitrary directed graphs. CG uses a unique graph parsing method to determine intrinsic substructures (clans) in the graph and to produce a parse tree. The tree is given attributes that specify the node layout. Through the use of clans as substructures, there are relatively few unnecessary edge crossings. Routing nodes are added that guarantee few bends in long edges, and long edges are shortened whenever possible.

CG is the first graph drawing tool to use a graph parsing as the fundamental structure that describes the node layout. Graph-grammar researchers have described schemes for graph layout that are similar to ours, but difficulties in graph-grammar parsing have inhibited their implementation. In particular, Brandenburg [4.] defines a layout graph grammar as a graph grammar together with a layout specification. The layout specification associates a finite set of layout constraints with each production. Our approach is to classify the productions of the graph parse and associate layout attributes with each production type in the parse tree of the graph.

The use of graph parsing distinguishes CG from all other general directed graph drawing schemes. The standard approachto automatic layout of directed graphs has three steps: 1. Assign nodes to layers; 2. reorder the nodes in each layer to reduce crossings; 3. Adjust the position of the nodes in each layer to reduce the number of bends. Usually the nodes are layered by distance from a source node. Our method also creates a hierarchical drawing where nodes and bends are constrained to lie on a set of equally spaces horizontal lines called layers [8., 14.]. CG groups subgraphs (clans) which have two-dimensional affinity in contrast to the one-dimensional constraints of the standard method. CG also reduces bends by placing routing nodes in their correct positions in the parse tree.