Research projects
Symmetries and graph isomorphism

Symmetries of Graphs and The Graph Isomorphism Problem

Symmetries of a graph are described by its automorphism group, consisting of all permutations of vertices preserving adjacencies and non-adjacencies called an automorphisms. Automorphism groups are closely related to the famous graph isomorphism problem which asks whether two graphs are the same up to a relabeling of vertices called an isomorphism.


Five platonic solids together with their automorphism groups.

For more information and detailed description of our results, see my PhD thesis Extension Properties of Graphs and Structures.

Jordan-like inductive characterizations

In 1869, Jordan pioneered the study of automorphism groups of trees. Very nice inductive description of these groups was stated by Babai (1991) as the class of groups closed under the direct product and the semidirect product with symmetric groups. We call such inductive characterizations as Jordan-like. By Frucht's theorem, every abstract group is isomorphic to the automorphism group of some graph. A graph class is called universal if for every abstract finite group, there exists a graph from the class having the isomorphic automorphism group, and non-universal otherwise.


Overview of some graph classes with understood automorphism groups. For definitions of these graph classes, see Chapter 1 of my PhD thesis.

In [1], we have described Jordan-like inductive characterizations for the automorphism groups of interval graphs, permutation graphs, and circle graphs. We develop a general technique interpreting automorphisms of geometrically represented graphs as morphisms of these representations. Therefore, the automorphism group Aut(G) can be studied by its induced action on the set of all geometric representations of G. When the structure of all geometric representations is captured by a tree data structure, we can use it to characterize the automorphism groups. This approach is closely related to the research project Geometric Representations of Graphs.


The action of the automorphism group of an interval graph on the structure of all its interval representations.

Babai (1972) described a non-inductive characterization of the automorphism groups of planar graphs. In [2], we give the first inductive characterization of these groups based on the aforementioned technique. First, we prove that stabilizers of vertices in connected planar graphs are precisely the class of groups closed under several group products with symmetric, cyclic, and dihedral groups. Next, we describe the automorphism groups of connected planar graphs by direct products of a spherical group with these stabilizers. For more detail, see Chapter 8 of my PhD thesis.

The graph isomorphism problem restricted by lists

Lubiw (1981) introduced the list-restricted graph isomorphism problem. The input gives two graphs G and H and a list L(u) of admissible images of each vertex u of G. We ask whether there exists a list-compatible isomorphism from G to H such that each vertex u of G is mapped to one of the admissible vertices of H. Surprisingly, Lubiw proved that this problem is NP-complete.


Two isomorphic trees G and H. There exists no list-compatible isomorphism because there is no perfect matching between the lists of the leaves of G and the leaves of H.

In [3], we revive the study of this problem for restricted graph classes and graph parameters. The goal is to find out which techniques used for graph isomorphism translate to the list restricted version. We prove the following results:

Metatheorem: [3] Polynomial-time reductions for GraphIso using vertex gadgets can be modified to polynomial-time reductions for ListIso. Therefore, GI-completeness results for GraphIso using such reductions imply NP-completeness of ListIso.

Theorem: [3] The problem ListIso can be solved in polynomial time for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs and bounded treewidth graphs.

Theorem: [3] The problem ListIso remains NP-complete for 3-regular colored graphs with all color classes of size at most 8 and with all lists of size at most 3.


Overview of our results in [3] for list-restricted graph isomorphism.

Regular covering testing

Graph covering is a topological notion of similarity of graphs. A big graph G covers a small graph H if and only if there exists a covering projection p from G to H which is a locally bijective homomorphism. This means that when u is mapped to p(u), then N[u] is mapped bijectively to N[p(u)], so the neighborhoods of u and p(u) look locally the same. Graph coverings are an important technique of algebraic graph theory since many graph properties and results for one of these graph automatically translate to the other one.


An example of a covering projection p from G to H where the images are determined by colors.

A covering projection is called regular if it can be described using certain symmetries of the big graph G. More precisely, if there exists a semiregular subgroup Γ of Aut(G) such that G / Γ ≅ H where the quotient graph G / Γ is created from vertex- and edge-orbits of the action of Γ. For instance, the above covering projection is regular where Γ is generated by the antipodal involution. In [4,5,6], we have pioneered the study of the computational complexity of regular covering testing.


All regular quotients of the cube.

In [4,5], we study structural properties of regular graph covering with respect to 1-cuts and 2-cuts in G. We show that our 3-connected reduction, described in research project Geometric Representations of Graphs, behaves well with respect to regular graph covers: by combining different possible regular quotients of 3-connected component, we obtain all regular quotients of the original graph. Since all quotients of 3-connected planar graphs can be easily understood from the geometry, we describe all possible quotients of all connected planar graphs. As a consequence, we give a new direct proof of Negami's Theorem:

Theorem: (Negami) For a connected planar graph G, every regular quotient of G is planar or projectively planar.

Also, our structural results are applied in [4,6] to construct the following involved algorithm for regular covering testing:

Theorem: [4,6] Let G and H be input graphs such that G is a planar graph. We can test whether G regularly covers H in time O(v(G)c 2e(H)/2) for some constant c where v(G) is the number of vertices of G and e(H) is the number of edges of H.

In other words, regular covering testing of planar graphs is in FPT when parameterized by the size of the small graph. In particular, we get a polynomial-time algorithm for every fixed graph H. This sharply contrast with our result [7] that general covering testing is NP-complete for planar graphs G even for several small fixed graph H. For a detailed description of these results, see Chapters 10 and 11 of my PhD thesis.

Selected publications

  1. Pavel Klavík, and Peter Zeman:
    Automorphism Groups of Geometrically Represented Graphs.
    Submitted, 2016.
    The conference version appeared in 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 540-553, 2015.
    Links: arXiv, proceedings link.
  2. Pavel Klavík, Roman Nedela, and Peter Zeman:
    Jordan-like Characterization of Automorphism Groups of Planar Graphs.
    Submitted, 2015.
    Links: arXiv.
  3. Pavel Klavík, Dušan Knop, and Peter Zeman:
    Graph Isomorphism Restricted by Lists.
    Submitted, 2016.
    Links: arXiv.
  4. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela:
    Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs.
    In Automata, Languages, and Programming, ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 489-501, 2014.
    Links: arXiv, proceedings link.
  5. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela:
    3-connected Reduction for Regular Graph Covers.
    The journal version of the structural part of [4], submitted, 2017.
    Links: arXiv.
  6. Jiří Fiala, Pavel Klavík, Jan Kratochvíl, and Roman Nedela:
    Algorithmic Aspects of Regular Graphs Covers.
    The journal version of the algorithmic part of [4], submitted, 2017.
    Links: arXiv.
  7. Ondřej Bílka, Jozef Jirásek, Pavel Klavík, Martin Tancer, and Jan Volec:
    On the Complexity of Planar Covering of Small Graphs.
    In Graph-Theoretic Concepts in Computer Science, WG 2011, volume 6986 of Lecture Notes in Computer Science, pages 83-94, 2011.
    Links: arXiv, proceedings link.