Seminár z teórie grafov - Roman Nedela (12.5.2016)

vo štvrtok 12.5.2016 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Roman Nedela (UMB Banská Bystrica, ZČU Plzeň)

Názov: Constructive approach to automorphism groups of planar graphs

Termín: 12.5.2016, 9:50 hod., M/213

Abstrakt:
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 the automorphism groups of planar graphs. In the talk, 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 obtained as semidirect product of a direct product of these stabilizers with a spherical group. As a result we get a characterization similar to the Jordan's characterization of automorphism groups of trees. 

Our approach is based on the decomposition to 3-connected components (a modified Trachtenbrot decomposition) and gives a quadratic-time algorithm for computing the automorphism group of a planar graph. 

This is a joint work with P. Klavik and P. Zeman.

 

---