Session B2 - Graph Theory and Combinatorics
July 14, 18:00 ~ 18:25
Enumeration of labelled 4-regular planar graphs
Universitat Politècnica de Catalunya, Spain - email@example.com
The enumeration of planar graphs and related classes of graphs is currently an active area of research. For the case of 4-regular planar graphs there are known schemes for exhaustive generation starting from some basic graphs, such as the graph of the octahedron, but no counting results up to now. We present here a complete solution to the enumeration of 4-regular planar graphs.
To obtain our results we follow the classical technique introduced by Tutte: take a graph rooted at a directed edge and classify the possible configurations arising from the removal of the root edge. This produces several combinatorial classes that are further decomposed, typically in a recursive way. The decomposition translates into a system of polynomial equations for the associated generating functions. Along the way, we have to deal with the enumeration of quadrangulations and other classes of planar maps.
Joint work with Marc Noy (Universitat Politècnica de Catalunya and BGSMath) and Clément Requilé (Freie Universität Berlin and Berlin Mathematical School).