Geometric symmetry in graphs

This thesis investigates the general problem of constructing meaningful drawings of abstract graphs, in particular the application of axial and rotational symmetry, collectively known as geometric symmetry, to achieving this goal. The problem of algorithmically constructing these visually-informative drawings presents two distinct challenges: firstly, a set of explicit and objective drawing criteria must be identified to direct their construction, and secondly, efficient computational techniques must then be developed to actually implement these criteria. Accordingly, a comprehensive list of criteria is introduced, and conflicts between various criteria are revealed. An extensive survey of existing work is then presented, making use of this list as a means of categorizing and comparing these known results. The construction of symmetric drawings is identified as one of the foremost criteria, since such drawings enable an understanding of the entire graph to be built up from that of a smaller subgraph, replicated a number of times. Formal definitions of drawings and geometric symmetry of graphs are presented, and some of their more important features are discussed. The fundamental problems of determining if a graph has any geometric symmetry, along with several variations, are all shown to be NP-complete in the case of general graphs. Consequently, attention focuses on symmetry in planar graphs. In the case of trees, outerplanar graphs, and embedded graphs, algorithms are successfully developed for detecting geometric symmetry and constructing related drawings, exhibiting the maximum number of simultaneously-displayable symmetries. All these algorithms run in time which is linear in the size of the graph, and hence are optimal. The thesis concludes by examining several open problems and potential directions for future research in graph drawing. In particular, the problem of drawing graphs which have no geometric symmetry is discussed, and modifications to the algorithms developed here are put forward to handle such cases