Space Optimized Graph Layout

Information Visualization is an important research branch of the visualization field. It is dedicated to the investigation and development of the visual approaches and interaction techniques which substantially enhance the user's cognition competence of the abstract, non-spatial information collections from the nature, science and the social practice. The modern Information visualization is an interdisciplinary study involving graphics, computer science and human-machine interaction etc.Both tree and graph are common mathematical models for defining and describing the information structures, in which the individual information contents are represented as the nodes (or vertices in graph) and the relationship between them represented as the edges. In information visualization, tree and graph could be visually displayed on the computer screen in, at least theoretically, any arbitrary abstract ways, as well as they can help users to view, analyze, explore or understand the underlying structural characteristics and regularity in the information, such as clustering features, small world effects, scale-free characteristics, etc.A lot of significant visualization models for layouting trees or graphs have been developed. The typical layout models for trees include the Classical Hierarchical View, H-Tree Layout, Radial View, Cone Tree, Tree-Maps, Hyperbolic Tree, etc. Famous graph layout methods include Spring Model, Kamada and Kawai'Algorithm, Force-Directed Algorithm, Davidson and Harel'Algorithm, etc. However, how to render large tree or complex network on the limited computer screen is still one of the key challenges facing information visualization.The thesis improves Space Optimized Tree algorithm on the space partition and aesthetic appearance. The improved Space Optimized Tree algorithm is then applied to the initial layout for graphs, especially for those graphs with clustering information, together with other layout adjustment algorithm to produce visual representation of graphs with nice utilization of space.The main works for this thesis are as follows:(1) Making a relatively detailed survey of tree and graph layout algorithms, analyzing the advantages and disadvantages of these methods, introducing the major challenges facing tree and graph visualization.(2) Improving the Space Optimized Tree algorithm on several aspects such as the space partitioning strategy and aesthetic appearance. In the modified method, a tree branch is positioned in a polygon with its area, rather than one angle of polygon, proportional to the branch size, making the space partition more reasonable and utilization rate of space better.(3) Applying the improved Space Optimized Tree algorithm to graph layout, especially clustering graph layout, presenting a new method for visualizing graphs.(4) Programming and testing the algorithms above with Java under the integrated development environment Netbeans 6.8. The experimental results demonstrate the feasibility of them.