Department of
Applied
Mathematics

Jordan-like characterization of automorphism groups of planar graphs (J. Matoušek prize talk)

Pavel Klavík

Abstract

In 1975, Babai characterized which abstract groups can be realized as the automorphism groups of planar graphs. In this paper, we give a more detailed and understandable description of these groups. 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. The automorphism group of a connected planar graph is then obtained as a semidirect product of a direct product of these stabilizers with a spherical group. The formulation of the main result is new and original. Moreover, it gives a deeper insight into the structure of the groups. As a consequence, automorphism groups of several subclasses of planar graphs, including 2-connected planar, outerplanar, and series-parallel graphs, are characterized. Our approach translates into a quadratic-time algorithm for computing the automorphism group of a planar graph which is the first such algorithm described in detail.