Abstract
This thesis explores the computational techniques necessary to efficiently realize certain optimal algorithms for the production of drawings which exhibit maximum axial and rotational symmetries of abstract graphs.
The problem of geometric symmetry detection for general graphs has been shown to be NP-complete. However, optimal algorithms have recently been established for the detection of symmetry in trees, outerplanar graphs, and embedded planar graphs. This thesis focuses on the utilization of these algorithms to efficiently produce maximally symmetric drawings of graphs from the classes of symmetric trees and outerplanar graphs.
The construction of symmetric tree drawings is presented first. Following a concise definition of the problem, optimal symmetry detection algorithms for trees are presented and the extent of the prior work is summarized. Computational techniques are examined to realize optimal implementations of these algorithms. Necessary to the present work, an extension to an established tree isomorphism algorithm is presented which should find applications in other areas of computational graph theory. Finally addressed is the nontrivial problem of symmetrically laying out a tree once its symmetries have been identified.
In the style of the tree presentation, symmetry algorithms are next examined for biconnected outerplanar graphs, and then for connected outerplanar graphs. Symmetry detection algorithms are discussed, techniques are investigated for realizing optimal implementations of the algorithms, and the problem of utilizing these algorithms to produce symmetric drawings is addressed. Finding the unique Hamilton cycle of a biconnected outerplanar graph is a fundamental part of the work, and a new algorithm is presented to solve this problem.
The thesis concludes with a summary of the symmetry algorithms realized and the critical issues encountered in the practical application of these algorithms to the problem of producing symmetric drawings.
Recommended Citation
Pacheco, R. T. and Manning, J. B., "Fast Symmetric Graph Drawing: Theory and Realization" (1991). Computer Science Technical Reports. 101.
https://scholarsmine.mst.edu/comsci_techreports/101
Department(s)
Computer Science
Report Number
CSc-91-19
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1991 University of Missouri - Rolla, All rights reserved
Publication Date
01 July 1991
Comments
*This report is substantially the M.S. thesis of the first author, completed July 1991.