
92 CHAPTER 3. SYMMETRIC GRAPH DRAWING
C
1
C
2
C
3
R
0
R
1
R
2
R
3
R
4
R
5
R
6
R
7
Figure 3.3 A cir cu lar grid.
(c) A can be displayed as a dihedral group if and only if all the following conditions
hold.
i. A is dihedral; that is, it has two generators α and ρ such that α
2
= 1, ρ
k
= 1
for some k > 1, and αρ = ρ
−1
α.
ii. |f ix
A
| ≤ 1.
iii. f ix
α
induces a set of disjoint paths.
iv. If ρ fixes an edge, then |fix
A
| = 0.
The proof of Theorem 3.2 is an algorithm, stated below, that takes a grap h G and an
automorphism grou p A satisfying the conditions of the theorem, and draws G to di sp lay A.
The drawing is on a circular grid as illustr ate d in Figure 3.3.