| Graphs are used to represent various types of information structures in computer science: e.g., telecommunication networks, databases, subroutine call graphs, VLSI circuits, and resource allocation maps. Graph visualization is the study of techniques for the automated layout of these structures onto a two or three dimensional space where each node is represented by a polygon or circle and each edge by a polygonal line. In this thesis, we explore multiple types of graph visualization. Our contributions are as follows. We present several O(m) time techniques for producing circular drawings of biconnected and nonbiconnected graphs on a single or multiple embedding circles. These algorithms are designed to produce drawings which have a small number of edge crossings and show connectivity. Our experimental results show that the above algorithms perform better than previous ones. We also introduce two polynomial time techniques for finding many small node-disjoint cliques in a given graph and an experimental study which shows their merit. Algorithms for creating force-directed and orthogonal drawings which highlight the existence of small cliques in the graph are also given. Results of experimental studies show these techniques to perform well with respect to multiple aesthetic criteria. We also present a technique for refining orthogonal graph drawings and results of an experimental study which show their performance over drawings created by five well known algorithms. Finally, we present an O( m) time algorithm for creating process diagrams, which are a special type of flowchart. |
