Frucht (1939) proved that every abstract finite group is isomorphic to the automorphism group of some finite graph. Jordan (1869) studied automorphism groups of trees. Babai (1991) gives an elegant inductive description of the automorphism groups of trees as the class of groups of closed under direct products and wreath products with symmetric groups. We call similar inductive characterizations of possible automorphism groups as Jordan-like.

We describe Jordan-like characterizations of the automorphism groups of several geometrically represented graph classes including planar, interval, permutation, and circle graphs. These characterizations are based on a general technique in which an automorphism group is studied by its induced action on the set of all geometric representations: each automorphism is either an automorphism of a representation, or a morphism of one representation into another one. When the structure of all representations is well understood (for instance, captured by a suitable tree decomposition) and the action is faithful enough, we can deduce the automorphism groups.

In my talk, I will illustrate this technique on the most complicated case of planar graphs. Babai (1975) characterized which abstract groups can be realized as the automorphism groups of planar graphs. We describe the first inductive Jordan-like characterization of these groups. We use the augmented 3-connected decomposition which divides a graph into its 3-connected components while capturing its symmetries, developed for our previous study of regular graph covers of planar graphs. The Jordan-like characterization first describes the stabilizers of vertices in connected planar graphs as the class of groups closed under the direct 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.

(joint work with Roman Nedela and Peter Zeman)