A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs

Hong, Seok-Hee and Eades, Peter (2004) A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 307-317 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_31).

Full text not available from this repository.

Abstract

This paper presents a linear time algorithm for constructing maximally symmetric straight-line drawings of biconnected and one-connected planar graphs. This research was partially supported by a grant from the Australian Research Council. For the full version of this paper, see [7,8]. National ICT Australia is funded by the Australian Governmentrsquos Backing Australiarsquos Ability initiative, in part through the Australian Research Council.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_31
Classifications:G Algorithms and Complexity > G.910 Symmetries
P Styles > P.720 Straight-line
P Styles > P.780 Symmetric
ID Code:597

Repository Staff Only: item control page

References

L. Babai, Automorphism Groups, Isomorphism, and Reconstruction, Chapter 27 of Handbook of Combinatorics Volume 2 (ed. Graham, Groetschel and Lovasz), Elsevier Science, 1995.

G. Di Battista and R. Tamassia, On-Line Planarity Testing, SIAM Journal on Computing 25(5), pp. 956-997, 1996.

P. Eades and X. Lin, Spring Algorithms and Symmetries, Theoretical Computer Science 240, pp. 379-405, 2000.

S. Hong, P. Eades and S. Lee, An Algorithm for Finding Geometric Automorphisms in Planar Graphs, Algorithms and Computation, Proc. of ISAAC 98, Lecture Notes in Computer Science 1533, pp. 277-286, Springer-Verlag, 1998.

S. Hong, P. Eades and S. Lee, Drawing Series Parallel Digraphs Symmetrically, Computational Geometry: Theory and Applicatons 17(3-4), pp. 165-188, 2000.

S. Hong, B. McKay and P. Eades, Symmetric Drawings of Triconnected Planar Graphs, Proc. of SODA 2002, pp. 356-365, 2002.

S. Hong and P. Eades, Drawing Planar Graphs Symmetrically II: Biconnected Graphs, Technical Report CS-IVG-2001-01, Basser Department of Computer Science, The University of Sydney, 2001, Submitted.

S. Hong and P. Eades, Drawing Planar Graphs Symmetrically III: One-connected Graphs, Technical Report CS-IVG-2001-02, Basser Department of Computer Science, The University of Sydney, 2001, Submitted.

S. Hong and P. Eades,Symmetric Layout of Disconnected Graphs, Algorithms and Computation, Proc. of ISAAC 2003, Lecture Notes in Computer Science 2906, pp. 405-414, Springer Verlag, 2003.

J. E. Hopcroft and J. K. Wong, Linear Time Algorithm for Isomorphism of Planar Graphs, Proc. of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172-184, 1974.

J. Manning, Geometric Symmetry in Graphs, Ph.D. Thesis, Purdue Univ., 1990.