Graph Drawing

Mohammad Ali Ebrahimi, Michael Monagan

POSTER: Drawing Graphs by Numerical Solution of a System of Second Order Ordinary Differential Equations

PAPER: A Graph Theory Package for Maple, Part II: Graph Coloring, Graph Drawing, Support Tools, and Networks.

In this paper we present the spring algorithm for drawing graphs of vertices and edges in 2D or 3D. Starting from random initial position for the vertices, the algorithm finds a local minimal total energy of the graph. While graph drawing is a complicated problem, this algorithm requires no special knowledge about the structure of the graph. This approach gives very good drawings of graphs. It is limited in that the complexity is inherently O(n^2) where n is the number of vertices in the graph.  Our implementation is effective for n up to about 100. The Maple implementation of this algorithm will be used by the Graph Theory Package.
We want our algorithm to find an aesthetic layout of the graph that clearly conveys its structure and assign a location for each node and a route for each edge, so that the resulting drawing is “nice”. To solve this problem we describe one such method that models a graph as a physical system that leads to a system of second order differential equations that needs to be solved. We Replace edges with springs (zero rest length). In addition we replace vertices with electrically charged particles. These particles repel each other. Furthermore we add damping to the physical system as a stabilizer factor.

In summary we are solving a system of differential equations which the equation for node i  is the following:

Where   is the position vector of the node i.

      This image describes the conversion of a graph to a physical model in our algorithm

For Example, for the graph  we have the following system:

With the Initial Values as follow:

We solve this system by the Fehlberg fourth-fifth order Runge-Kutta method (RKF45) with degree four interpolant. This can be done in Maple by the dsolve[numeric] command.

In order to reconstruct good graphs from the randomly positioned initial vertices it is important that the spring model is not over damped nor under damped. Since we are solving the system of differential equations numerically, in case of over damped or under damped, reaching to the local minimum is almost impossible. To correct this we choose the damping constant, spring constant, and repelling constants carefully. After experimenting with different graphs we have concluded that a dynamic model with respect  to different graphs is required.

Damping constant:
we suggest that the value of damping constant is proportional to the degree of each node. For example if we have a node with three springs connected to it then there is more damping required for that node.
Spring and repulsion Constants:
We suggest that the value of the spring constant and also repulsion constant are directly related. For example if we increase the strength of the spring then we need to have stronger repulsion force. However the relation between the spring and repulsion constant is not linear. We suggest the ratio of  where A is the repulsion constant, B is the spring constant, and n is the number of nodes in the graph. On the other hand if we have a node with a high degree then the repulsion force should be small on this node and consequently less force for our spring.

In summary   ,    , where  is the degree of node i.

Results: