Drawing, Manipulating, and Recognizing Graphs

发布于:2021-07-23 11:09:31

Drawing, Manipulating, and Recognizing Graphs

M. S. Krishnamoorthy, F. Oxaal, U. Dogrusoz, D. Pape, A. Robayo, R. Koyanagi, Y. Hsu, D. Hollinger and A. Hashmi Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180. February 11, 1995
In this paper, we describe di erent methods for three dimensional embedding of graphs, as well as a two dimensional layout method, namely barycentric embedding. In addition, we present a program for automatic recognition of graphs. We nally describe servers for graph drawing routines that can be called from C or C++ programs and applications such as Mosaic. Keywords: Graph theory, educational tool, visualization of graphs, embedding graphs, manipulating graph embeddings, recognition of graphs, client/server model.


1 Introduction
GraphPack is an educational package 4] developed at Rensselaer that provides users with the capability to study and visualize graph theoretic algorithms. The graphical user interface is built on X windows. This application can manipulate both digraphs and graphs, and can draw them under di erent embeddings. GraphPack itself is composed of two components: the kernel and Xgraphpack. The kernel has an interpreter that accepts Lila (Little Language) commands from the user and communicates with Xgraphpack. Xgraphpack, on the other hand, is an X window program that draws graphs and performs certain operations on them (i.e., by clicking on prede ned buttons) such as browsing, grouping, fetching and saving. Figures 1 and 2 are examples of some of the capabilities of GraphPack. We encourage the reader to contrast Figure 2 with Figure 14 on page 35 of 3]. Please refer to 2] for several other graph manipulation systems. The next section is dedicated to the description of 3-d and 2-d layout algorithms. The common goal of the 3-d algorithms presented is to evenly spread a given number of points on the surface of a sphere so that they could be viewed three-dimensionally. The idea is that it may be possible to visually represent graphs in a way which increases our ability to think about them. An even spreading is one in which the great circle distance between any two neighboring points is the same. Such even spherical spreadings are geometrically impossible in most cases. Thus, the algorithms
Supported in part by the National Science Foundation under Grant Number CDA-8805910.


Figure 1: A graph of a soccer ball in 2-d planar layout.


Figure 2: Groupings of all pentagons of the soccer ball in Figure 1 resulting in an icosahedron.


here must nd \good" approximate solutions as opposed to exact solutions. Since the algorithms are motivated by graph visualization, their implementation is within a special graphical viewing environment, namely GraphPack. This environment allows the user to rotate the points around each of three coordinate axes, and to permute graph vertices so that more visually palpable con gurations could be found. The 2-d layout algorithm, on the other hand, utilizes barycentric embedding of Tutte 6]. We embed an outer cycle of a speci ed length, which can be chosen by the user. In section 3, we present a method to identify the vertices and edges of an undirected unlabeled graph from the physically scanned images of a printed graph. The printed graph is obtained from x g (with its interface to GraphPack). We scan the image, identify the vertices and edges, and store the resultant graph with its positions in GraphPack format. In addition, GraphPack contains a feature that provides data communication between itself and other related applications such as Maple 1], Mathematica 5], and Matlab. From a computer network approach, this feature allows GraphPack to be a client and the other application to be a server. In other words, GraphPack is able to send requests (commands) to other applications which in turn service the request and return a result. The aim of a server in this sense is three-fold: 1. To make GraphPack act as a server. This will grant users exibility when interfacing with GraphPack by writing a multimedia animation program for coloring. This is accomplished by the ability to send commands to GraphPack without setting up a communication mechanism and with a minimal knowledge of LiLa. 2. To write multimedia graph programs with ease of of portability. 3. To provide a drawing facility within Mosaic framework. This feature of GraphPack is described in section 4, which is followed by a nal section of concluding remarks.

2 Layout
We will rst describe three di erent 3-d layout methods followed by a description of a 2-d layout method, namely barycentric method.

2.1 3-d Layout Methods

Three di erent methods for spreading points on a sphere are presented here: 1. populating evenly spaced lines of latitude, 2. incremental point repulsion, 3. subdivision of octahedron and random subtraction.



Lines of Latitude Population

The algorithm rst builds a table showing how many circles of latitude are needed to accommodate n number of vertices such that the latitudinal di erence between the circles is the same as the longitudinal di erence between the points. After the table is built, a graph is read into an array, and the number of vertices is used to look up the proper number of circles of latitude to spread the vertices out onto. These circles will lie at even increments of latitude. We then cycle through the circles of latitude, populating them with graph vertices using the same longitudinal spacing for each vertex. As we cycle through, the altitude and azimuth of each vertex is generated, which is then converted to normalized vector coordinates. Normalization of the vectors causes all points to lie one unit from the origin thereby forming a sphere. The table is built as follows: 1. Divide a sphere into progressively larger numbers of equally spaced circles of latitude. 2. At each new number, add up the total circumference of all the circles. 3. Now, there will be a maximum of the numbers of vertices which can be spread on all the circles such that the longitudinal spacing of the points is the same as the latitudinal spacing between the circles (simply divide the total circumference by the latitudinal angle between the circles). 4. Enter that maximum number into the table. Now, the number of lines of latitude needed is simply a table look up based on the number of vertices in the graph. A vector may now be generated for each vertex based on the number of circles of latitude which when divided into 180 degrees gives us the latitudinal angle between them { which is in turn used as the value to longitudinally space the vertices along each circle. The problem with this method is that when the number of latitude lines increases by 1, the number of vertices needed to ll the new latitude line is more than 1. Thus, for graphs with many vertices, it will often be the case that the circle of latitude closest to the north pole will not be completely lled with vertices. Figure 3 shows an example of this method for a cube graph of eight vertices.
2.1.2 Point Repulsion

In this method, points are randomly distributed on a sphere and then caused to repel each other in small increments until the distance between each set of neighbors is above a certain threshold. This threshold is arrived at through experimentation. The maximum value it can take is the cap angle of the cap which has surface area equal to the surface area of the sphere divided by the number of points to be spread out. This number will be a little too big in most cases, and if used, will cause the algorithm to loop forever. Thus, an experimentally derived smaller number is used. Since the algorithm is not guaranteed to terminate, the program will automatically exit if a speci ed 5

Figure 3: Lines of latitude population method for a cube.


maximum number of times through the loop is reached. The algorithm on average takes (n2 ) steps to compute. An example of point repulsion method is given in Figure 4.
2.1.3 Subdivision

An octahedron has 6 vertices, and 8 equilateral triangular faces. If each face is replaced by four faces by dividing each edge in half and connecting the dots, then 8 triangles become 32 triangles and 6 vertices become 18 vertices. In general, each subdivision produces 4 times the number of triangles previously existed and the number of vertices is related to the number of triangles by the following formula: number of vertices = (3 number of triangles ? 24)=6+6 (for a tetrahedron the formula would be (3 number of triangles ? 12)=6+4:) Here, the desired number of vertices is obtained by rst subdividing an octahedron until the needed number is exceeded, and then subtracting vertices at even intervals until the needed number is reached. Thus by the table below, if 112 vertices are needed, 258 vertices would have to be generated rst, and then 146 of them subtracted. Level of Recursion Number of Triangles Number of Vertices 1 8 6 2 32 18 3 128 66 4 512 258 5 2048 1026 6 8192 4098 Of course, the main problem here is that since many subtractions are needed in most cases, the evenness of the octahedron distribution is compromised. In order to implement this, an existing utility was located, which generates the three vertices of each of the triangles produced by the subdivision described above. Thus, for example, at recursion level two, this utility produces the (normalized) coordinates of 3 32 or 96 points. Many of these points are duplicates. To obtain the 18 unique points, the output must be sorted and ltered using the Unix sort and uniq utilities. An example of this method can be found in Figure 5.
2.1.4 Observations

\How can complex graphs be viewed intelligibly on two-dimensional surfaces?" Some e orts have focused on displaying such graphs as projections of three-dimensional wireframe objects. Such e orts fail when too many graph edges cross through the volume de ned by the wireframe object. Such an object when projected produces an unintelligible jumble of criss-crossing lines on the two-dimensional viewing surface. There are four possible solutions: 1. Allow the user to interactively rotate the object in three dimensions, thereby adding more \visual bandwidth" to the two-dimensional viewing medium. 2. Use stereoscopic technology to clarify which edges are behind other edges whose projections intersect.


Figure 4: Point repulsion on a cube.


Figure 5: Subdivision method for a cube.


3. Intelligently spread the vertices of the graph and reorder the edges, so that two-dimensional projections are optimized for intelligibility. 4. Use some visual representation of the graph other than wireframe to either replace the wireframe approach, or supplement it. The e ort here implements options 1 and 3 without the \intelligence." Motion, when added as a dimension to visual communication, adds \visual bandwidth." Objects which are ambiguous when viewed statically may be resolved when the information which motion provides is added. However, for wireframe objects, sometimes even motion is not enough. Options 2 and 4 would address this problem.

2.2 A 2-d Layout Method: Barycentric Method
0 0

The basic idea of the barycentric method is that each location should be the average of its neighbors' locations; the algorithm was devised by Tutte 6]. A set of vertices are given xed positions, which are then used to compute the positions of the remaining vertices. This is done by solving the systems linear equations Mx = x and My = y . M is a k k matrix, where k is the number of vertices that were not initially positioned. It is based on the graph's adjacency matrix: M = ?1 if vertices i and j are adjacent, 0 otherwise. The vectors x and y are computed from the vertices that were initially positioned; x is equal to the sum of the x coordinates of the vertices adjacent to unpositioned vertex i and y uses the sums of the y coordinates. Solving the two systems of equations will give the locations of the unpositioned vertices. The vertices whose locations are xed initially can be selected in three ways. By default, the program will nd any arbitrary cycle of the graph and use those vertices, placing them in a circle. Another way is to let the user specify a required length for the cycle. If no cycle of that length exists, the drawing routine returns failure. Thirdly, the user may select speci c vertices and place them where desired, and the locations of the remaining vertices will be computed from them. Figures 6, 7, and 8 show examples of barycentric method with di erent lengths of cycles.
0 0 0



3 Undirected Graph Recognizer
Our program can extract the logical meaning of an undirected graph given the bit-mapped image of the graph. In other words, given a picture of a graph, our program can generate a list of vertices, edges, and a connection table. The requirements of our program is that the graph be distinctly drawn, with lled circles for vertices and straight lines for edges. The image of the graph is expected to be solid black on white (no grayscale or dithering allowed). The program rst localizes the vertices by nding scan lines of consecutive dark pixels (i.e. corresponding to the areas of the circle near the diameter), and then seeks edges between pairs of vertices. The slopes of the edges adjacent to each vertex are calculated, and the next nearest vertex in that direction is found yielding an edge between this vertex and the original one. This calculation is done for each vertex in order to nd the complete adjacency list. 10

Figure 6: Barycentric method with an outercyle of length 4 for a cube.


Figure 7: Barycentric method with an outercyle of length 6 for a cube.


Figure 8: Barycentric method with an outercyle of length 8 for a cube.


Figure 9: Picture of an arbitrary graph (a cube). For example, from the raster image of the graph in Figure 9, the recognizer produced the following output in GraphPack format.
VERTICES:{1,2,3,4,5,6,7,8} VWEIGHTS:*1,1,1,1,1,1,1,1* EDGES:{{1,5},{1,4},{1,2},{2,6},{2,3},{3,7},{3,4},{4,8},{5,8},{5,6},{6,7},{7,8}} EWEIGHT:*1,1,1,1,1,1,1,1,1,1,1,1*

The following are the vertex pixel co-ordinates corresponding to this graph (note that this layout corresponds to the graph in Figure 6 in GraphPack, which is the same as the original graph).
(25,270) (166,269) (235,337) (236,481) (237,56) (237,198) (306,269) (447,270)

4 Servers
In this section, we describe the client/server model for calling drawing routines as well as utilizing them from within Mosaic framework.

4.1 Implementation

The important aspect is the data communication between a user's program and GraphPack. Sockets, which handle data communication e ciently, are used for this purpose. This communication is extended into a client/server model as illustrated below. Consequently, the project is split into 14

three les: \client.c", \server.c", and \user.c". The server sets up the socket connection for the kernel and executes Loopback which is an existing application to execute both kernel and Xgraphpack. The client contains functions to execute the server, set up the socket connection for the user's program, send Lila commands to the kernel, and kill the server and GraphPack when nished. Here is the pseudo-code for each of the three functions mentioned in an outline form. Server (server.c): Set up the address for the socket; Open and bind the socket; Listen for the client; if client does not connect within TIMEOUT seconds exit(); Accept the socket; fork(); Child process: Redirect I/O to the socket; execl(Loopback); Parent process: waitpid(for child process); (client.c): gethostname(); fork(); Child process: execl(executable le of server.c); Parent process: Set process group to be the leader of all subsequent Graphpack processes; sleep(3) to allow the child process time to open the socket; Set up the socket address; Connect with the socket; switch input to init server: case 0: check if the graph input le exists and then call display(); case 1: nothing; case 2: call make graph(); case 3: call input graph(); Functions: send cmd(): display(): exit server(): error(): cont(): make graph(): input graph():



(user.c: contains a sample program to compute the Hamiltonian path of a graph) init server(); Convert the input le to an adjacency list of vertices; Initialize P N] (Array to hold vertices in the path) and H N] M] (Array where entries in row n are forbidden to vertex n); while (!done) for each vertex V connected to the rst vertex; Try to extend the path with the conditions: V is not in the P array; V's value must be larger than the rst vertex; V can not be closed to the last vertex in P; (This is checked with the H array). if the three conditions are true Add V to the P array; Color the edge and announce the two vertices; end for loop; if the P array contains all the vertices Color the last edge and announce the two vertices; done++; (Hamiltonian path found) else if all the vertices connected to the rst vertex have been checked done++; (No Hamiltonian path found) else (Backtrack) Color the previous edge back to white; Reset the H array; endwhile; exit server();

This client/server feature strengthens GraphPack's ability to provide useful services for a variety of users. In addition, with the aid of animation and sound (sound animations are done through the sound facility provided by the Sun systems using C interface) for visualizing the computation, GraphPack is even a more useful tool in the study of graph theory. We created an experimental GraphPack server by interfacing Xmosaic to GraphPack through an HTTP server running a cgi-bin script written in PERL. Upon entry to the interface document, an Xmosaic user is presented a form to ll out including information about the X window display name currently in use. Once the user completes the form, the resulting URL request is sent to our HTTP server, which then starts up a GraphPack session and sends the window to the X window display indicated. This experimental service provides full access to all of the features of GraphPack, but usage is limited because of the security issues involved. 16

4.2 Interface to Mosaic

5 Concluding Remarks
In this paper, we presented drawing and recognition capabilities of an educational package, GraphPack. We also discussed how it can be used as part of a client/server model from and within C or C++ programs and other applications such as Maple, Mathematica, Matlab, and Mosaic. GraphPack is ideally suited for creation, drawing, and manipulation of graphs with not more than thirty vertices. It does not seem to be as e cient and well suited for graphs with seventy or more vertices though. Currently, we are exploring to overcome this limitation. Another improvement we plan to make on this package is the exibility of having vertices of di erent sizes and shapes in the same graph.

1] B.W. Char et al. , Maple V Language Reference Manual, Springer Verlag, 1991. 2] N. Dean and G. Shannon (eds), Computational Support for Discrete Mathematics, Vol. 15, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Publications, 1994. 3] D. E. Knuth, The Stanford Graph Base, Addison Wesley, MA 1993. 4] M. Krishnamoorthy et al., "Improvements to GraphPack: A System to Manipulate Graphs and Digraphs", in Computational Support for Discrete Mathematics and Theoretical Computer Science, Vol. 15, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Publications, 1994, pp. 279-296. 5] S. Skiena, Implementing Discrete Mathematics, Addison Wesley, Redwood City, CA., 1990. 6] W. T. Tutte, "How to Draw a Graph", "Proc. London Math Soc. Vol. 3, No. 13, 1963.