
3.5. SYMMETRIC DRAWINGS OF PLANAR GRAPHS 107
Figure 3.15 Di s pl ay of two maximal planar automorphism groups.
This means that additional maximal planar automorphism groups only add a constant
to the time complexity of the algorithms.
3.5.5 Drawing algorithms
The algorithms presented in the preceding sections take a planar graph as input and produce
two outputs : a planar automorphism group of maximum size, and an embedding of the
graph. In this section, we show how to use this information to const r u ct a straight-line
symmetric drawing of the graph. The drawing algorithms follow the same connectivity
hierarchy.
For triconnected graphs, one could