A Method for Graph Drawing Utilising Patterns

This thesis describes a novel method for the layout of undirected graphs. It works by identifying certain patterns within the graph and drawing these in a consistent manner. For graphs to be useful and of benefit to a user, the result must clear and easy to understand. This process attempts to draw graphs in such a manner.

Firstly, a background of graph problems and graph drawing is introduced, before the benefits of patterns are explained. Following this, there is an in-depth discussion of a number of existing graph drawing techniques, perceptual theories and methods for subgraph isomorphism.

This pattern-based method is then explained in great detail. Firstly, the patterns required are defined and examples given. Then, there is an explanation of the methodology involved in identifying these patterns within a graph. Following on from this, the order in which patterns are drawn based on their connection types to those already drawn is detailed, before a detailed description of each drawing method.

Evaluation of this method follows, starting with analysis mainly based on three real world data sources. This is in the form of side-by-side comparisons of graphs drawn with this method and a force-directed method. Following this, a metric based evaluation compares the two methods on edge crossings and occlusion, while also detailing some pattern based metrics.

Further evaluation continues in the form of an empirical study. The methodology of this study is detailed before results are displayed. Analysis of these results follows, with conclusions drawn.

Finally, potential further work is detailed and possible implementations discussed. All study materials and results are provided in the Appendix for those who wish to repeat the study or analysis.