Testing Planarity of Geometric Automorphisms in Linear Time

It is a well-known result that testing a graph for planarity and, in the affirmative case, computing a planar embedding can be done in linear time. In this paper, we show that the same holds if additionally we require that the produced drawing be symmetric with respect to a given automorphism of the graph. This problem arises naturally in the area of automatic graph drawing, where symmetric and planar drawings are desired whenever possible. An extended abstract of this paper has been published in the proceedings of ISAAC 2002 (Lecture Notes in Computer Science, vol. 2518, pp. 563–574, 2002). The first author is supported by the Marie Curie Research Training Network ADONET 504438 funded by the EU. This paper was partially written when he was visiting the University of Sydney. The second author was supported by a grant from the Australian Research Council. National ICT Australia is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.