Vortrag
Enumeration of 4-regular planar graphs
Vortrag von Prof. Dr. Marc Noy
Sprecher eingeladen von: Prof. Dr. Valentin Féray
Datum: 09.06.17 Zeit: 11.15 - 12.15 Raum: Y27H28
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.
In the talk we will discuss the main ideas in our solution, without entering into the technical details, which involve a considerable number of combinatorial classes and huge algebraic equations.
This is joint work with Clément Requilé and Juanjo Rué.