Three-dimensional visualization of multi-layered graphs with application to communications

Abstract

This thesis introduces two new algorithms for 3D graph drawing and network display. The first algorithm, the Incremental Projection Algorithm , is a new universal algorithm for displaying any graph of any vertex degree. The above algorithm can be implemented to display graph in 3D space without edge crossing. The number of edge bends produced by the algorithm does not excess two. The average time complexity of the Incremental Projection Algorithm is O( N N), where N is the number of vertices in a graph. If there is no degree of vertices great than M, the time complexity of the Incremental Projection Algorithm is O(N). The second algorithm is called Depth-Height Buffer Algorithm. The algorithm is designed for displaying special multi-layered networks. Actually, the algorithm is a method for hidden object elimination. It is useful for multi-layered communication networks visualization. The time complexity of the Depth-Height Buffer Algorithm is O(N log N) . Two demonstration packages of the above algorithms are developed in order, to verify their correctness and functionality. The thesis also discusses the methods and techniques for 2D graph drawing. In bi-layered crossing reduction aspect the thesis presents a new method called the minimizing angle approach, which may reduce the crossings among the edges with the time complexity of O(|S |max(|N|,|S |)).