CountGraph – Marie Curie Career Integration Grant FP7 PEOPLE- 2013-CIG 630749

Enumeration of discrete structures: algebraic, analytic, probabilistic and algorithmic methods for enriched planar graphs and planar maps

Brief summary

Recently the interest in planar maps and graphs has considerably increased, due to fundamental constructions by Schaeffer (bijections for planar maps in terms of enriched tree structures), and Giménez and Noy (generating function techniques joint with analytic tools). Our objective is to continue the lines of these achievements and explore their interactions with other domains, specially with computer science.

More precisely, the main goals of this project are to develop new tools to deal with open questions in the field, including the study of bipartite families of graphs, unlabelled families of graphs, and planar graphs with restricted vertex degrees, among other questions. In most of the cases, the interaction between the map enumeration domain and the algorithmic setting will be strongly explored.

The main techniques exploited in this project arise from the Analytic Combinatorics setting: that is, the combinatorial structure is translated into equations of generating functions, that can be studied by means of complex analytic methods, joint with probabilistic techniques.

Permanent members

Juanjo Rué (Principal investigator, FU Berlin, Germany)
Clément Requilé (FU Berlin, Germany)


Variants of Plane Diameter Completion
Proceedings of IPEC 2015
Petr Golovach, Clément Requilé, Dimitrios Thilikos

Subgraph statistics in subcritical graph classes
Michael Drmota, Lander Ramos

4.- Pentagonal chains and annuli as models for designing nanostructures from cages

Journal of Mathematical Chemistry 54 (3) (2016), 765-776

Josep Oliva, Andrey A. Dobrynin, Vladimir Rosenfeld

Spanning trees in random series-parallel graphs
Advances in Applied Mathematics 75 (2016): 18-55
Julia Ehrenmuller

Many 2-level polytopes from matroids
Discrete & Computational Geometry 54 (3) (2015):954-979

Francesco Grande

On the limiting distribution of the metric dimension for random forests

European Journal of Combinatorics 49 (2015): 68-89
Dieter Mitsche


The following researchers had collaborated in different levels in the development of the objectives of the project:

Francesco Grande (FU Berlin, Germany)
Michael Drmota (TU Wien, Austria)
Dieter Mitsche (Université de Nice, France)
Lander Ramos (UPC Barcelona, Spain)
Marc Noy (UPC Barcelona, Spain)
Petr Golovach (Bergen U., Norway)
Julia Ehrenmüller (TUHH, Hamburg, Germany)
Vincent Pilaud (CNRS and École Polytechnique, France)
Dimitrios Thilikos (CNRS and Kaposdistrias Univ.)
Kerstin Weller (ETH Zürich, Switzerland)


The CountGraph Project has been present (in different levels) in the following conferences and events:

Berlin-Poznan-Hamburg Seminar (May 2015)