Automorphism Groups of Maps in Linear Time

In a seminal paper from 1974, tarjan and wong (stoc’74) proved that one can decide in linear timewhether two planar graphs are isomorphic. building on tarjan-wang’s approach and on further work bykawarabayashi and the speaker (stoc’08), we extend these results and show that the automorphismgroup of any map (a 2-cell embedded graph) can be found in linear time. the speaker will show thesubtleties in the case of spherical maps. this is joint work with ken-ichi kawarabayashi, roman nedela,and peter zeman