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)
Publications
Variants of Plane Diameter Completion Proceedings of IPEC 2015 | Petr Golovach, Clément Requilé, Dimitrios Thilikos | |
Subgraph statistics in subcritical graph classes Submitted | Michael Drmota, Lander Ramos | |
4.- Pentagonal chains and annuli as models for designing nanostructures from cages |
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 |
Francesco Grande | |
On the limiting distribution of the metric dimension for random forests European Journal of Combinatorics 49 (2015): 68-89 |
Dieter Mitsche |
Collaborators
The following researchers had collaborated in different levels in the development of the objectives of the project:
Conferences
The
CountGraph Project has been present (in different levels) in the
following conferences and events:
Berlin-Poznan-Hamburg
Seminar (May 2015)