Abstract
Constructing a visually informative drawing of an abstract graph is a problem of considerable practical importance, and has recently been the focus of much investigation. Displaying symmetry has emerged as one of the foremost criteria for achieving good drawings. Linear-time algorithms are already known for the detection and display of symmetry in trees, outerplanar graphs, and embedded planar graphs. The central results of this paper show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete. A number of related results are also established, including the #P-completeness of counting the axial or rotational symmetries of a graph.
Recommended Citation
Manning, Joseph, "Computational Complexity of Geometric Symmetry Detection in Graphs" (1990). Computer Science Technical Reports. 17.
https://scholarsmine.mst.edu/comsci_techreports/17
Department(s)
Computer Science
Report Number
CSc-90-1
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1990 University of Missouri--Rolla, All rights reserved.
Publication Date
22 Jan 1990
Comments
This paper was presented at the First Great Lakes Computer Science Conference, held at the University of Western Michigan, October 1989. The paper has been submitted for publication in the conference Proceedings, which will appear in the Lecture Notes in Computer Science series by Springer-Verlag.