Drawing Graphs:Symmetric Drawing

Symmetric Drawing

A graph drawing can have two kinds of symmetry: axial (or reflectional) symmetry and rotational 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 for drawing series-parallel digraphs symmetrically [17].

In this section we briefly describe a linear time algorithm to draw triconnected planar graphs with maximum symmetry. Note that the algorithm of Tutte described in Section 46.3.1 can be used to construct symmetric drawings of triconnected planar graphs, but it does not work in linear time. Here we give the linear time algorithm of Hong, McKay and Eades [18]. It has two steps:

1. Symmetry finding: this step finds symmetries, or so-called geometric automor- phisms [12], in graphs.

2. Symmetric drawing: this step constructs a drawing that displays these automor- phisms.

More specifically, the symmetry finding step finds a plane embedding that displays the maximum number of symmetries. It is based on a classical theorem from group theory called the orbit-stabilizer theorem [2]. It also uses a linear time algorithm of an algorithm of Fontet [14] to compute orbits and generators for groups of geometric automorphisms. For details, see [18]. Here we present only the second step, that is, the drawing algorithm. This constructs a straight-line planar drawing of a given triconnected plane graph such that given symmetries are displayed.

The drawing algorithm has three routines, each corresponding to a type of group of symmetries in two dimensions:

1. the cyclic case: displaying k rotational symmetries;

2. one axial case: displaying one axial symmetry;

3. the dihedral case: displaying 2k symmetries (k rotational symmetries and k axial symmetries).

The dihedral case is important for displaying maximum number of symmetries, however it is the most difficult to achieve. Here, we concentrate on the first two cases; the cyclic case and the one axial case. In Section 46.4.1, we describe an algorithm for constructing a drawing displaying rotational symmetry and in Section 46.4.2 we describe an algorithm for constructing a drawing displaying axial symmetry. We briefly comments on the dihedral case in Section 46.4.3.

The input of the drawing algorithm is a triconnected plane graph; note that the outside face is given. Further, the algorithm needs to compute a triangulation as a preprocessing step. More specifically, given a plane embedding of triconnected planar graphs with a given outside face, we triangulate each internal face by inserting a new vertex in the face and joining it to each vertex of the face. This process is called star-triangulation and clearly it takes only linear time.

A major characteristic of symmetric drawings is the repetition of congruent drawings of isomorphic subgraphs. The algorithms use this property, that is, they compute a drawing for a subgraph and then use copies of it to draw the whole graph. More specifically, each symmetric drawing algorithm consists of three steps. First, it finds a subgraph. Then it draws the subgraph using the algorithm of Chiba et al. [6] as a subroutine. The last step is to replicate the drawing; that is, merge copies of the subgraphs to construct a drawing of the whole graph.

The application of Theorem 46.2 is to subgraphs of a triconnected plane graph defined by a cycle and its interior. In that case Thomassen’s conditions can be simplified. Suppose that P is a path in a graph G; a chord for P in G is an edge (u, v) of G not in P , but whose endpoints are in P .

COROLLARY 46.1 Let G be a triconnected plane graph and let S be a cycle of G. Let W be the graph consisting of S and its interior. Let S∗ be a drawing of S as a convex k-gon (where S might have more than k vertices). Let P1, P2,... , Pk be the paths in S corresponding to the sides of S∗. Then S∗ is extendable to a straight-line planar drawing of W if and only if no path Pi has a chord in W .

Proof We can assume that the interior faces of W are triangles, since otherwise we can star triangulate them.

We need to show that Thomassen’s three conditions are met. Condition 1 is a standard implication of the triconnectivity of G, and Condition 3 follows just from the observation that the internal vertices have degree at least 3.

To prove the first part of Condition 2, suppose on the contrary that C is a connected component of W − S which is adjacent to Pi but not to any other of P1,... , Pk . Let u and v be the first and last vertices on Pi which are adjacent to C. If u = v, or u and v are adjacent on Pi, then {u, v} is a cut (separation pair) in G, which is impossible as G is triconnected. Otherwise, there is an interior face containing u and v and so u and v are adjacent contrary to our hypothesis (since the internal faces are triangles).

The second part of Condition 2 is just the condition that we are imposing.

Displaying Rotational Symmetry

Firstly, we consider the cyclic case, that is, displaying k rotational symmetries. Note that after the star-triangulation, we may assume that there is either an edge or a vertex fixed by the symmetry. The fixed edge case can only occur if k = 2 and this case can be transformed into the fixed vertex case by inserting a dummy vertex into the fixed edge with two dummy edges. Thus we assume that there is a fixed vertex c.

The symmetric drawing algorithm for the cyclic case consists of three steps.

The second step, Draw Wedge Cyclic, constructs a drawing D of the wedge W using Algorithm ConvexDraw, such that P1 and P2 are drawn as straight-lines. This is possible by the next lemma.

LEMMA 46.1 Suppose that W is the wedge computed by Algorithm Find Wedge Cyclic, S is the outside face of W , and S∗ is the drawing of the outside face S of W using three straight-lines as in Figure 46.9(a). Then S∗ is extendable to a planar straight-line drawing of W .

Proof One of the three sides of S∗ corresponds to part of the outside face of G, which cannot have a chord as G is triconnected.

The other two sides cannot have chords either, as they are shortest paths in G. Thus W and S∗ satisfy the conditions of Corollary 46.1.

The last step, Merge Wedges Cyclic, constructs a drawing of the whole graph G by replicating the drawing D of W , k times. Note that this merge step relies on the fact that P1 and P2 are drawn as straight-lines. This is illustrated in Figure 46.9 (b).

Clearly, each of these three steps takes linear time. Thus the main result of this section can be stated as follows.

THEOREM 46.5 Algorithm Cyclic constructs a straight-line drawing of a triconnected plane graph which shows k rotational symmetry in linear time.

Displaying Axial Symmetry

A critical element of the algorithm for displaying one axial symmetry is the subgraph that is fixed by the axial symmetry. Consider a drawing of a star-triangulated planar graph with one axial symmetry. There are fixed vertices, edges and/or fixed faces on the axis. The subgraph formed by these vertices, edges and faces, is called a fixed string of diamonds.

The first step of the algorithm is to identify the fixed string of diamonds. Then the second step is to use Algorithm Symmetric Convex Draw, a modified version of Algorithm ConvexDraw. Thus Algorithm One Axial can be described as follows.

Algorithm One Axial

1. Find a fixed string of diamonds. Suppose that ω1, ω2,..., ωk are the fixed edges and vertices in the fixed string of diamonds, in order from the outside face (ω1 is on the outside face). For each £, ω£ may be a vertex or an edge. This is illustrated in Figure 46.10.

2. Choose an axially symmetric convex polygon S∗ for the outside face of G.

3. Symmetric ConvexDraw(1, S∗, G).

The main subroutine in Algorithm One Axial is Algorithm Symmetric Convex Draw. This algorithm, described below, modifies Algorithm Convex Draw so that the following three

conditions are satisfied.

1. Choose v in Step 1 of Algorithm Convex Draw to be ω1. In Algorithm Convex Draw, v must be a vertex; here we extend Algorithm Convex Draw to deal with an edge or a vertex. The two cases are illustrated in Figure 46.11.

2. Let D(Bi) be the drawing of Bi and α be the axial symmetry. Then, D(Bi) should be a reflection of D(Bj ), where Bj = α(Bi ), i = 1, 2,... ,m and m = lp/2J.

3. If p is odd, then D(Bm+1) should display one axial symmetry.

It is easy to see that satisfying these three conditions ensures the display a single axial symmetry.

Using the same argument as for the linearity of Algorithm Convex Draw [6], one can show that Algorithm One Axial takes linear time.

THEOREM 46.6 Algorithm One Axial constructs a straight-line drawing of a triconnected plane graph which shows one axial symmetry in linear time.

Displaying Dihedral Symmetry

In this section, we briefly review an algorithm for constructing a drawing displaying k axial symmetries and k rotational symmetries.

As with the cyclic case, we assume that there is a vertex fixed by all the symmetries. The algorithm adopts the same general strategy as for the cyclic case: divide the graph into “wedges”, draw each wedge, then merge the wedges together to make a symmetric drawing. However, the dihedral case is more difficult than the pure rotational case, because an axial symmetry in the dihedral case can have fixed edges and/or fixed faces. This requires a much more careful applications of the Algorithm Convex Draw and Algorithm Symmetric Convex Draw; for details see [18].

Nevertheless, using three steps above, a straight-line drawing of a triconnected plane graph which shows dihedral symmetry can be constructed in linear time.

In conclusion, the symmetry finding algorithm together with the three drawing algorithms ensures the following theorem which summarizes their main result.

THEOREM 46.7 (Hong, McKay and Eades [18]) There is a linear time algorithm that constructs maximally symmetric planar drawings of triconnected planar graphs, with straight-line edges.