Symmetric Drawings of Planar Graphs in Two Dimensions


Seok-Hee Hong, Brendan McKay and Peter Eades, A Linear Time Algorithm for Constructing Maximally Symmetric Straight-line Drawings of Triconnected Planar Graphs, Discrete and Computational Geometry, 36 (2), pp. 283-311, 2006, Springer.

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. To draw graphs symmetrically, we need two steps. The first step is to find appropriate automorphisms. The second step is to draw the graph to display the automorphisms. Our aim in this paper is to construct maximally symmetric straight-line drawings of triconnected planar graphs in linear time. Previously known algorithms run in quadratic time. We show that an algorithm of Fontet can be used to find an embedding in the plane with the maximum number of symmetries, and present a new algorithm for finding a straight line drawing that achieves that maximum. Both algorithms run in linear time.



Seok-Hee Hong and Peter Eades, Drawing Oneconnected Planar Graphs Symmetrically, Algorithmica, 44 (1), pp. 67-100, 2006, Springer.

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a planar drawing of G. Finding planar automorphisms is the first and most difficult step in constructing planar symmetric drawings of graphs. The problem of determining whether a given graph has a nontrivial geometric automorphism is NP-complete for general graphs.
The two previous papers in this series have discussed the problem of drawing planar graphs with a maximum number of symmetries, for the restricted cases where the graph is triconnected and biconnected. This paper extends the previous results to cover planar graphs that are oneconnected. We present a linear time algorithm for drawing oneconnected planar graphs with a maximum number of symmetries.

    
        



Seok-Hee Hong and Peter Eades, Drawing Biconnected Planar Graphs Symmetrically, Algorithmica, 42(2), pp. 159-197, 2005, Springer.

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals the structure in the graph. This paper discusses symmetric drawings of biconnected planar graphs. More specifically, we discuss geometric automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a drawing of G. Finding geometric automorphisms is the first and most difficult step in constructing symmetric drawings of graphs. The problem of determining whether a given graph has a non-trivial geometric automorphism is NP-complete for general graphs. In this paper we present a linear time algorithm for finding planar geometric automorphisms of biconnected planar graphs. A drawing algorithm is also discussed.

        



Seok-Hee Hong and Peter Eades, Symmetric Layout of Disconnected Graphs, Algorithms and Computations, Proceedings of ISAAC 2003 (Algorithms and Computations), Lecture Notes in Computer Science, Springer, 2003, pp. 405-414, 2003.

We present a linear time algorithm for drawing disconnected planar graphs with maximum number of symmetries. Our algorithm can be generalized to making symmetric arrangements of bounded disjoint objects in the plane.