“Automated display techniques for linear graphs” by Maguire

The development of display procedures for drawing pictures of linear graphs is described. The facility to model relationships pictorially has led to the use of graph theoretic techniques in many different applications. While computers normally work with a numeric representation of a graph such as its incidence matrix, manual transformation of such representations into pictures is a tedious process. An interactive graphics system has been developed which, through a combination of heuristic techniques and semi-automatic procedures, creates visual representations of graphs with a minimum of user intervention. The resultant pictures display mirror-image and rotational symmetries that occur within the graph. This very general approach of displaying symmetry in graphs has proven useful in studies of several classes of graphs. However, the system is primarily a research tool designed for use by mathematicians and graph theorists. Difficulties entailed in adapting the display procedures to more specific application areas are discussed.

1. Chang, Manning and Metze. Fault Diagnosis of Digital Systems. Wiley, 1970.
2. Faulkner, Gary Bruce. Recursive Generation of Cyclically K-Connected Cubic Planar Graphs. Ph. D. Thesis, Department of Combinatorics and Optimization, University of Waterloo (1971).
3. Friedman, Daniel P., Dickenson, David C., Fraser, John J., and Pratt, Terrence W. GRASPE 1.5: A Graph Processor and its Applications. Department of Computer Science, University of Houston (1969).
4. Hurwitz and Citron. GRAF: Graphic Additions to FORTRAN. Proceeding SJCC 1967, 553-558.
5. IBM System/360 Component Description IBM 2250 Display Unit Model 1. Form A27-2701-2, IBM Data Processing Division, White Plains, N. Y.
6. Tutte, W. T. How to Draw a Graph. Proceedings London Mathematical Society 13 (1963), 743-767.
7. Unger, S. H. GIT-A Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism. Comm. ACM 7, 1 (Jan. 1964), 26-34.
8. Weyl, Herman, Symmetry. Princeton University Press, 1952.
9. Wolfbert, Michael S. An Interactive Graph Theory System. Moore School Report No. 69-25, University of Pennsylvania (June 1969).