Drawing Graphs Symmetrically in Three Dimensions

Hong, Seok-Hee (2002) Drawing Graphs Symmetrically in Three Dimensions. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 189-204 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_16).

Full text not available from this repository.

Abstract

In this paper, we investigate symmetric graph drawing in three dimensions. We show that the problem of drawing a graph with a maximum number of symmetries in three dimensions is NP-hard. Then we present a polynomial time algorithm for finding maximum number of three dimensional symmetries in planar graphs.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_16
Classifications:P Styles > P.780 Symmetric
G Algorithms and Complexity > G.910 Symmetries
P Styles > P.060 3D
ID Code:510

Repository Staff Only: item control page

References

L. Babai. Automorphism groups, isomorphism, and reconstruction. Chapter 27 of Handbook of Combinatorics, vol. 2, (Ed. Graham, Groetschel and Lovasz), Elsevier Science, 1995.

S. Bachl. Isomorphic subgraphs. In Proc. Graph Drawing, volume 1731 of Lecture Notes in Computer Science, pages 286-296, 1999.

G. Di Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algoritmica 15, pages 302-318, 1996.

H. Chen, H. Lu, and H. Yen. On maximum symmetric subgraphs. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS, pages 372-383. Springer, 2001.

P. Eades and X. Lin. Spring algorithms and symmetry. Theoretical Computer Science, 240(2):379-405.

H. de Fraysseix. A heuristic for graph symmetry detection. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., pages 276-285, Berlin. Springer, 1999.

S.-H. Hong, P. Eades, and S.-H. Lee. Drawing series parallel digraph symmetrically. Computational Geometry: Theory and Applications, vol. 17, issue3-4, pages 165-188, 2000.

S.-H. Hong, P. Eades, and S.-H. Lee. An algorithm for finding geometric automorphisms in planar graphs. In K.-Y. Chwa and O. H. Ibarra, editors, Proc. Algorithms and Computation (ISAAC '98), volume 1533 of Lecture Notes in Comput. Sci., pages 277-286, Berlin, 1998. Springer.

S.-H. Hong and P. Eades. An algorithms for finding three dimensional symmetry in trees. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS, pages 360-371. Springer, 2001.

S.-H. Hong, P. Eades, and S.-H. Lee. An algorithm for finding three dimensional symmetry in series parallel digraphs. Algorithms and Computation, LNCS 1969, (Ed. D.T. Lee and S. Teng), pages266-277, Springer-Verlag, 2000.

J. Hopcroft and and J.K. Wong. Linear time algorithm for isomorphism of planar graphs. Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pages 172-184, 1974.

R.J. Lipton, S.C. North, and J.S. Sandberg. A method for drawing graphs. In 'proc. 1st Annu ACM Sympos. Comput. Geom., pages 153-160, 1985.

A. Lubiw. Some NP-complete problems similar to Graph Isomorphism, SIAM Journal on Computing 10(1):11-21, 1981.

P. Mani. Automorphismen von polyedrischen graphen. Math. Annalen, 192, pages 279-303, 1971.

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

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

J. Manning. Geometric Symmetry in graphs. PhD thesis, Purdue University, 1990.

G.E. Martin. Transformation geometry, an introduction to symmetry. Springer, New-York, 1982.