Drawing Graphs:Symmetric Drawing
Symmetric Drawing A graph drawing can have two kinds of symmetry: a x ia l (or reflectional) symmetry and r o t a tional symmetry. For example, see Figure 46.8 . The drawing in Figure 46.8(a) displays four rotational symmetries and Figure 46.8(b) displays one axial symmetry. Figure 46.8(c) displays eight symmetries, four rotational symmetries as well as four axial symmetries. Manning [28] showed that, in general, the problem of determining whether a given graph can be drawn symmetrically is NP-complete. De Fraysseix [9] presents heuristics for symmetric drawings of general graphs. Exact algorithms for finding symmetries in general graphs were presented by Buchheim and Junger [5], and Abelson, Hong and Taylor [1]. There are linear time algorithms available for restricted classes of graphs. Manning and Atallah present a liner time algorithm for detecting symmetries in trees [26], outerplanar graphs [27], and plane graphs [28]. Hong, Eades and Lee present a linear time algorithm