Drawing Planar Graphs Symmetrically, II: Biconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graphdrawing because it reveals the structure in the graph. This paperdiscusses symmetric drawings of biconnected planar graphs. Morespecifically, we discuss geometric automorphisms, that is,automorphisms of a graph G that can be represented as symmetriesof a drawing of G. Finding geometric automorphisms is the firstand most difficult step in constructing symmetric drawings ofgraphs. The problem of determining whether a given graph has anon-trivial geometric automorphism is NP-complete for generalgraphs. In this paper we present a linear time algorithm forfinding planar geometric automorphisms of biconnected planargraphs. A drawing algorithm is also discussed.