An Heuristic for Graph Symmetry Detection

De Fraysseix, Hubert (1999) An Heuristic for Graph Symmetry Detection. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 276-285 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_28).

Full text not available from this repository.

Abstract

We give a short introduction to an heuristic to find automorphisms in a graph such as axial, central or rotational symmetries. Using techniques of factorial analysis, we embed the graph in an Euclidean space and try to detect and interpret the geometric symmetries of the embedded graph. It has been particularly developed to detect axial symmetries.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_28
Classifications:G Algorithms and Complexity > G.910 Symmetries
G Algorithms and Complexity > G.999 Others
ID Code:356

Repository Staff Only: item control page

References

J. P. Benzécri and et al, L'analyse des données - Tome II: l'analyse des correspondances, Dunod, Paris, 1973.

M. Capobianco, Examples and counterexamples in graph theory, Elsevier, North Holland, New York, 1978.

C. N. R. S. (ed.), L'analyse factorielle et ses applications, Paris, 1956.

D. G. Corneil and C. C. Gotlieb, An efficient algorithm for graph isomorphism, Journal of the ACM 17 (1970), no. 1, 51-64.

H. de Fraysseix and P. Ossona de Mendez, Discovering automorphisms using abstract distances, Tech. report, KAM-DIMATIA Series, 1999, (in preparation).

H. de Fraysseix and Kuntz P., Pagination of large scale networks, Algorithms review 2 (1992), no. 3, 105-112.

I. S. Filotti and J. N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus (working paper), Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (Los Angeles, California), 1980, pp. 236-243.

S. L. Hakimi and S. S. Yau, Distance matrix of a graph and its realizability, Quaterly of Applied Mathematics 22 (1964), 305-317.

S-H. Hong, P. Eades, and S-H. Lee, Finding planar geometric automorphisms in planar graphs, ISAAC 98 (ed. Chwa and Ibarra), Springer Lecture Notes in Computer Science 1533 (1998), 277-286.

S-H. Hong, P. Eades, and S-H. Lee, Drawing series parallel digraphs symmetrically (to appear).

J. E. Hopcroft and J. K. Wong, Linear time algorithm for isomorphism of planar graphs (preliminary report), Conference Record of Sixth Annual ACM Symposium on Theory of Computing (Seattle, Washington), 1974, pp. 172-184.

J. B. Kruskal and J. B. Seery, Designing network diagrams, Proceedings of the First General Conference on Social Graphics, 1978, pp. 22-50.

P. Kuntz, Représentation euclidienne d'un graphe en vue de sa segmentation, Ph. D. thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1992.

G. S. Lueker and S. B. Kellogg, A linear time algorithm for deciding interval graph isomorphism, Journal of the ACM 26 (1979), no. 2, 183-195.

J. Manning, Geometric symmetry in graphs, Ph. D. thesis, Purdue University, New York, 1990.

J. Manning and M. J. Atallah, Fast detection and display of symmetry in trees, Congress Numerantium 64 (1988), 159-169.

J. Manning and M. J. Atallah, Fast detection and display of symmetry in outerplanar graphs, Discrete Applied Mathematics 39 (1992), 13-35.

G. L. Miller, Isomorphism testing for graphs of bounded genus, Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (Los Angeles, California), 1980, pp. 225-235.

G. L. Miller, Isomorphism of graphs which are pairwise k-separable, Information and Control 56 (1983), no. 1/2, 21-33.

G. L. Miller, Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus, Information and Control 56 (1983), no. 1/2, 1-20.