ABSTRACT
Symmetry is one of the most important aesthetic criteria that clearly reveals the structure and properties of a graph. Graphs in textbooks on graph theory are normally drawn symmetrically. In some cases, a symmetric drawing may be preferred over a planar drawing. As an example, consider the two drawings of the same graph in Figure 3.1 (from [KK89]). The left drawing has five edge crossings, but eight symmetries (four rotations and four reflections). On the right is a planar drawing; it only has axial symmetry. Most people prefer the drawing on the left. As another example, the Petersen graph is normally drawn as in Figure 3.2. This drawing shows ten symmetries (five rotations and five reflections). In fact, it can be shown that a drawing of the Petersen graph can have at most ten symmetries, and Figure 3.2 is maximally symmetric. Of course, every drawing has the trivial symmetry, the identity mapping on the plane.
The aim of symmetric graph drawing is to draw a graph with nontrivial symmetry. More ambitiously, we aim to draw a graph with as much symmetry as possible. Symmetries of a drawing of a graph G are clearly related to the automorphisms of G;
intuitively, a symmetry of a drawing of G induces an automorphism of the graph. For example, in Figure 3.2, a rotational of the plane by 2π/5 is a symmetry of the drawing and induces the automorphism (0, 1, 2, 3, 4)(5, 6, 7, 8, 9). A reflection of the plane in a vertical axis induces the automorphism (1, 4)(6, 9)(7, 8)(2, 3). The automorphism group of a graph G defines its “combinatorial symmetries.” However, not every automorphism can be represented as a symmetry of a drawing of G. For example, the automorphism group of the Petersen graph has 120 elements, but, as mentioned above, a drawing can display only ten
Figure 3.1 Two drawings of the same graph: a planar drawing with eight symmetries and five edge crossings, and a planar drawing with an axial symmetry [KK89].
