Abstract

Graph drawing is the problem of representing graphs visually. How to efficiently represent graphs for visualization and intuition, as well as the pure beauty of the interplay between graph theory and geometry, has been investigated by mathematicians for centuries. Methodologies for creating graph displays have typically focused on drawing the graph on a two-dimensional surface. Today, interest in computer-based visualization has increased attention on methodologies for the display of graphs in three dimensions. A dynamic layout algorithm designed by Szirmay-Kalos takes a description of a graph G = ( V, E ) and assigns coordinates to the vertices and edges so that the graph can be drawn by a graphics program. The algorithm is based on physical simulation of an analogous mechanical system in which the vertices correspond to particles and the presence or absence of edges correspond to driving forces among these vertices. From the initial configuration of the vertices, the system is replacing them in such a way so that the local forces exerted on a vertex for all vertices are at minimum, which is defined as stable state of the system. Allowing the system to reach the stable state in three dimensions would enable the use of interactive computer visualization as a tool in revealing the graph's structure. The purpose of this Report is to describe the algorithm introduced by Szirmay-Kalos and discusses the utilization of this algorithm in three dimensions.