Automorphism Groups of Planar Graphs

Pavel Klavík, Roman Nedela

Published 2015-06-22Version 1

By Frucht's Theorem, every abstract finite group is isomorphic to the automorphism group of some graph. In 1975, Babai characterized which of these abstract groups can be realized as automorphism groups of planar graphs. In this paper, we give a more detailed description of these groups in two steps. First, we describe stabilizers of vertices in connected planar graphs as the class of groups closed under the direct product and semidirect products with symmetric, dihedral and cyclic groups. Second, the automorphism group of a connected planar graph is obtained as semidirect product of a direct product of these stabilizers with a spherical group. Our approach connects automorphism groups with geometry of planar graphs and it is based on a reduction to 3-connected components, described by Fiala et al. [ICALP 2014].