Éric Fusy

I am a CNRS researcher at LIX, Ecole Polytechnique. My main fields of research are enumerative combinatorics and algorithmics on combinatorial structures (such as random generation, compact encoding, graph drawing).

Articles and Preprints:

• A simple model of trees for unicellular maps,   with Guillaume Chapuy and Valentin Feray
  Building on the recursive bijection of the first author, we derive a bijection between unicellular maps and simple combinatorial structures called C-decorated trees, which are plane trees decorated by permutations with signed cycles of odd lengths. The genus of the map is very easy to read on the C-decorated tree, making it possible to recover already known counting formulas for unicellular maps in a unified bijective framework. In particular we give the first bijective proof of the Goupil-Schaeffer formula (counting bipartite unicellular maps with control on the white vertex degrees and black vertex degrees) and give a simple bijective interpretation of the Harer-Zagier recurrence (by an extension of the Remy's procedure for plane trees).
  • Long version, Journal of Combinatorial Theory, Ser. A, 120(8): 2064-2092 (2013) pdf
  • Short version, FPSAC´12. pdf

• Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings,   with Luca Castelli Aleardi and Olivier Devillers
  We extend the straight-line drawing algorithm of de Fraysseix, Pollack and Pach (using the notion of canonical ordering) to triangulations on the cylinder; the drawing being periodic in x. Then, by a simple reduction from the torus to the cylinder (using a so-called tambourine) we can also obtain a periodic (in x and y) drawing algorithm for triangulations on the torus.
  • Graph Drawing'12. pdf

• A simple formula for the series of constellations and quasi-constellations with boundaries,   with Gwendal Collet
  We show a general formula for the series of bipartite (and quasi-bipartite) maps with boundaries of prescribed lengths. In the case of two and three boundaries we recover expressions obtained recently by Eynard, in the case where the whole sphere is covered by the boundary faces we recover Tutte´s slicings formula. A nice feature of our formula is that the expression factorizes as a constant factor and a series-factor that only depends on the total boundary length and the number of boundaries. The formula naturally extends to constellations and quasi-constellations.
  • Long version, submitted. pdf
  • Short version (with results limited to bipartite and quasi-bipartite maps), FPSAC´12. pdf

• Combinatorics of locally optimal RNA secondary structures,   with Peter Clote
  We show that for two simple energy models (Nussinov energy and base-stacking energy), the locally optimal RNA secondary structures can be enumerated exactly and asymptotically in a unified combinatorial setting.
  • To appear in Journal of Mathematical Biology. pdf

• The number of intervals in the m-Tamari lattices,   with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle
  The Tamari lattice is a standard lattice on Dyck paths (on binary trees, a local move in the lattice corresponds to a certain rotation at a node). In this article we consider for any m\geq 1 a natural generalization of the Tamari lattice to so-called m-Dyck paths, which correspond to (m+1)-ary trees; we call it the m-Tamari lattice (the case m=1 corresponds to the usual Tamari lattice). We prove that the number of intervals (for paths with n up steps) in the m-Tamari lattice is \frac{m+1}{n(mn+1)}{(m+1)^2 n+m\choose n-1}, which generalizes a formula found by Chapoton in the case m=1.
  • Electronic Journal of Combinatorics 18(2), P31 (2012). pdf

• Unified bijections for maps with prescribed degrees and girth,   with Olivier Bernardi
  Using the master construction presented in a preceding article, we present unified bijections for planar maps with control on the face-degrees and on the girth (the girth being the length of a shortest cycle). At first we give bijections for plane maps (one root-face) where the girth d equals the degree of the root-face. Then we give more general constructions for maps with two root-faces of arbitrary degrees and with control on two girth parameters (for cycles separating the root-faces and cycles not separating the root-faces, respectively). The bijections associate a bicolored decorated tree to a map, such that each non-root face of degree k in the map corresponds to a black vertex of degree k in the tree. Our constructions unify several already known bijections (for 1-legged maps, eulerian maps, loopless triangulations, etc.).
  • Journal of Combinatorial Theory, Ser. A, Vol 119(6), pp 1351-1387 (2012). pdf

• On symmetric quadrangulations and triangulations,   with Marie Albenque and Dominique Poulalhon
  This note consists of two (quite independent) parts. In the first one a new method for counting rooted simple quadrangulations and triangulations is given, based on quotienting a symmetric quadrangulation (resp. triangulation) in two different ways. In the second part, closely relying on results by Bouttier Di Francesco and Guitter, we obtain the expression of the series counting several families of symmetric quadrangular and triangular dissections, with control on the distance of the central vertex to the outer boundary.
  • Long version, European Journal of Combinatorics 35:13-31 (2014). pdf
  • Short version containing only results for quadrangulations. Eurocomb'2011. pdf

• Schnyder decompositions for regular plane graphs and application to drawing,   with Olivier Bernardi
  Schnyder introduced a structure now called "Schnyder woods", which consists in partitioning the inner edges of a planar triangulation into 3 spanning trees. We show that the concept can be generalized to d-angulations of girth d, for any d\geq 3: a d-angulation of girth d admits a covering of its inner edges by d oriented forests each with d-2 sinks and with specific crossing relations. As an application, in the case d=4, we give a planar orthogonal drawing algorithm for 4-regular plane graphs, such that each edge (except for two incident to the root-vertex) has exactly one bend.
  • Algorithmica 62(3-4): 1159-1197 (2012). pdf

• A bijection for triangulations, quadrangulations, pentagulations, etc.,   with Olivier Bernardi
  We introduce a general bijective construction for planar maps, which can be specialized to count several map families. We apply our bijective strategy to the families of d-angulations of girth d (simple triangulations for d=3, simple quadrangulations for d=4) possibly with a boundary of length p\geq d. In the cases d=3 or 4 we recover bijectively counting formulas by Brown. In the case d>4 the enumerative results are new to our knowledge.
  • Journal of Combinatorial Theory, Ser. A. 119(1) 218-244 (2012). pdf
  • Short version containing only results for d=3 or 4, under the title "A unified bijective approach for maps; application to two classes with boundaries"; FPSAC'10. pdf

• On the diameter of random planar graphs,   with Guillaume Chapuy, Omer Giménez, and Marc Noy
  We show that the diameter D(G_n) of a random (unembedded) labelled connected planar graph with n vertices is asymptotically almost surely of order n^{1/4}, in the sense that there exists a constant c>0 such that P(D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) for \e small enough and n large enough. We prove similar statements for rooted 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
  • Long version, submitted. pdf
  • Short version. Proceedings of the 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings, vol.AM (2010) 65-78. pdf

• Asymptotic study of subcritical graph classes,   with Michael Drmota, Mihyun Kang, Veronika Kraus, and Juanjo Rué
  We present a unified general method for the asymptotic study of graphs from the so-called "subcritical" graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works both in the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of parameters (number of edges, of vertices of fixed degree,...) of random graphs chosen from subcritical classes.
  • SIAM Journal on Discrete Math 25(4): 1615-1651 (2011). pdf

• Asymptotic enumeration and limit laws for graphs of fixed genus,   with Guillaume Chapuy, Omer Giménez, Bojan Mohar, and Marc Noy
  It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S_g of genus g grows asymptotically like $c^{(g)}n^{5(g-1)/2-1}\gamma^n n!$ where $c^{(g)}>0$, and $\gamma \approx 27.23$ is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gimenez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case.
  • Journal of Combinatorial Theory Ser. A 118(3): 748-777 (2011) pdf

• Optimal encoding of triangular and quadrangular meshes of fixed topology,   with Luca Castelli Aleardi and Thomas Lewiner
  A general bijective strategy first introduced by Poulalhon and Schaeffer and then generalized by Bernardi makes it possible to encode a planar map by a "canonical" spanning tree based on certain orientations. We apply this strategy to triangulations with boundaries, first in the planar case, then in higher genus (these correspond to the incidences vertices/edges/faces of triangular meshes on surfaces with boundaries). We have not succeeded to characterize nor count the encoding trees associated to such triangulations, but we can encode them optimally, ie., with number of bits matching (asymptotically) the entropy. Similar results can be obtained for bipartite quadrangulations.
  • Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010), pages 95-98, 2010. pdf

• Bijective counting of involutive Baxter permutations
  Using bijective correspondences with non-intersecting triples of lattice paths, we enumerate involutive Baxter permutations according to various parameters; in particular we obtain a direct proof that the number of involutive Baxter permutations of size $2n$ with no fixed element is $\frac{3\cdot 2^{n-1}}{(n+1)(n+2)}\binom{2n}{n}$, a formula originally discovered by M. Bousquet-M\'elou using generating functions. The same coefficient also enumerates acyclic orientations with a unique source on (unrooted) planar maps with $n$ edges, such that the source and sinks are in the outer face.
  • 7th Conference on Lattice path combinatorics and applications (2010). pdf

• Asymptotic enumeration of orientations,   with Stefan Felsner and Marc Noy
  We find the asymptotic number of 2-orientations of quadrangulations with n inner faces, and of 3-orientations of triangulations with n inner vertices. We also find the asymptotic number of prime 2-orientations (no separating quadrangle) and prime 3-orientations (no separating triangle). The proofs are based on singularity analysis of D-finite generating functions, using the Fuchsian theory of complex linear differential equations.
  • Discr. Math. and Theor. Comp. Sci. (DMTCS) 12:2 (2010) 249-262. pdf

• Counting elements and geodesics in Thompson's group F,   with Murray Elder and Andrew Rechnitzer
  We provide a very efficient algorithm for the exact enumeration of elements in Thompson's group F according to the geodesic length. This leads us to conjecture that the growth rate of the counting sequence is $(3+sqrt{5})/2$. We also propose a new algorithm for the exact enumeration of elements in any finitely generated group according to the geodesic length. This algorithm requires only polynomial memory if a certain word problem for the group has polynomial complexity.
  • Journal of Algebra. 324: 102-121 (2010). pdf

• Schnyder woods for higher genus triangulated surfaces, with applications to encoding,   with Luca Castelli Aleardi and Thomas Lewiner
  We show that the notion of Schnyder woods (in the plane, a partition of the edges into 3 spanning trees with specific incidence relations) can be defined and efficiently calculated for higher genus triangulated surfaces. The 3 spanning trees in the plane become here 3 spanning cellular embedded graphs, one of which has exactly one face.
  • Long version, Discrete and Computational Geometry 42(3): 489-516 (2009) pdf
  • Short version, Proceedings of the 24th Annual Symposium on Computational Geometry (SoCG'08), pages 311-319. pdf

• Baxter permutations and plane bipolar orientations,   with Nicolas Bonichon and Mireille Bousquet Mélou
  We describe here a direct bijection between Baxter permutations and plane bipolar orientations, which has several nice properties: it behaves well with respect to symmetries, and it specializes as a bijection between pattern avoiding permutations and nonseparable maps.
  • Séminaire Lotharingien de Combinatoire, B61Ah (2010), 29 pp. pdf

• Bijections for Baxter Families and Related Objects,   with Stefan Felsner, Marc Noy and David Orden
  This article presents in a unified setting several bijections relating families of structures counted by Baxter numbers, such as plane bipolar orientations, 2-orientations on quadrangulations, and Baxter permutations.
  • Journal of Combinatorial Theory Ser. A 118(3): 993-1020 (2011). pdf

• A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components,   with Guillaume Chapuy, Mihyun Kang and Bilyana Shoilekova
  We recover in this article several recent important results on graph enumeration (in particular planar graphs) in a unified setting. For this purpose we write down a complete decomposition grammar for a graph family into 3-connected components. This grammar yields a more direct combinatorial way to find the analytic expressions of Gimenez and Noy for the series counting planar graphs. Our methodology seems to be a promising tool toward the difficult task of counting unlabelled planar graphs. Indeed, the grammar involves no rooting/unrooting operations, so it lifts important technical difficulties (integration on series) that arose previously in the process of counting graphs.
  • Electronic Journal of Combinatorics, Volume 15(1), R148, 2008. pdf

• New bijective links on planar maps via orientations
  This article introduces new bijective relations on planar maps of increasing complexity. First we establish bijective relations on certain bipolar orientations, which in turn yield a bijection between 2-connected maps and irreducible triangulations, which in turn yields a recursive bijection between loopless maps and triangulations. Compared to classical map-to-map correspondences such as the duality relation, our constructions have the original feature that they make use of specific orientations, while still operating on the map in a simple local way.
  • Long version, European Journal of Combinatorics 31(1): 145-160 (2010) pdf
  • Short version, FPSAC'08 pdf

• Bijective counting of plane bipolar orientations and Schnyder woods,  with Dominique Poulalhon and Gilles Schaeffer
  The number of plane bipolar orientations with fixed numbers of vertices and faces satisfies a nice formula that has been found by Baxter from manipulations on generating functions of planar maps weighted by their Tutte polynomials. We provide a simple combinatorial proof of the formula, by introducing a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with specific endpoints. We also prove that bijection due to Bonichon and then reformulated by Bernardi and Bonichon is a specialization of our construction
  • Long version, European Journal of Combinatorics 30(7): 1646-1658 (2009) pdf
  • Short version. Proceedings of EuroComb 2007 (Sevilla), Electronic Notes in Discrete Mathematics 29, pp 283-287 (2007). pdf

• HyperLogLog, the analysis of a near-optimal cardinality estimation algorithm,  with Philippe Flajolet, Olivier Gandouet, and Frederic Meunier
  This article introduces a new probabilistic algorithm for the estimation of cardinality (i.e., number of distinct elements) of large multisets, with applications to traffic monitoring and statistical analysis of large data sets (e.g. DNA sequences). Compared to the classical LogLog algorithm developed by Flajolet and Durand, the probabilistic estimate is based on the Harmonic mean rather than Geometric mean, with the effect of adjusting the pic of the distribution of the estimator closer to the exact value of the cardinality.
  • Proceedings of the AofA'07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127-146 (2007). pdf

• Boltzmann samplers, Pólya theory, and Cycle-pointing,  with Manuel Bodirsky, Mihyun Kang and Stefan Vigerske
  A fruitful approach for counting structures in a combinatorial class is to instead consider the rooted class, which is easier to count because the root gives a starting point for a recursive decomposition. In this article we adapt the method to the unlabelled setting, where we have to deal with symmetries. We introduce a pointing operator (called cycle-pointing) which is unbiased, in the sense that each unlabeled unrooted structure of size n gives rise to n unlabeled pointed structures. We illustrate how this approach can be applied to enumerate several families of unlabeled structures and to obtain efficient random generators on such classes.
  • Long version, SIAM Journal on Computing 40(3): 721-769 (2011). pdf.
  • Short version, under the title "An unbiased pointing operator for unlabeled structures, with applications to counting and sampling". Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), New Orleans 2007, SIAM press, pages 356-365. pdf

• Estimating the number of Active Flows in a Data Stream over a Sliding Window ,  with Frederic Giroire
  It is often possible to extract informations (such as a certain parameter value) from huge data sets using only a very small auxiliary memory, provided one just aims at an estimate (not exact value) of the parameter with small relative error. This article focuses on the computation of the number of distinct flows in a data stream of packets. This information is useful to detect attacks such as Denial Of Service. In the context of telecommunications, the set of packets is in fact a stream, meaning that the estimate has to be maintained over a sliding window. We extend here the probabilistic algorithm MinCount (Giroire AofA'05) in that setting, and provide a full analysis of the complexity, which ensures that the auxiliary memory remains surprisingly small. The algorithm has been validated on internet traffic traces.
  • Proceedings of the Fourth Workshop on Analytic Algorithms and Combinatorics (ANALCO'07), New Orleans 2007, SIAM press, pages 223-231. pdf

• Boltzmann sampling of unlabelled structures,  with Philippe Flajolet and Carine Pivoteau
  This article extends the framework of Boltzmann sampling to classical constructions specific to the unlabelled case, namely multiset, powerset and cycle. The specificity of these constructions is that they are subject to symmetries. From the expressions of the generating functions, it is possible to guess how to assemble Boltzmann samplers for each of the constructions, giving rise to a very general sampling dictionary for unlabeled classes. In this way, several classes can be sampled, e.g. non plane rooted trees, integer partitions, acyclic alcohols, ...
  • Proceedings of the Fourth Workshop on Analytic Algorithms and Combinatorics (ANALCO'07), New Orleans 2007, SIAM press, pages 201-211. pdf

• Random sampling of plane partitions,  with Olivier Bodini and Carine Pivoteau
  This article introduces random generators of plane partitions. Combining a bijection of Pak with the framework of Boltzmann samplers, we obtain an approximate-size and an exact-size sampler for plane partitions that have expected complexity respectively O(n ln(n)^3) and O(n^4/3) (under a real-arithmetic computation model). To our knowledge, these are the first polynomial-time samplers for plane partitions according to the size. The same principles yield efficient samplers for (p x q)-boxed plane partitions (plane partitions with two dimensions bounded).
  • Combinatorics, Probability and Computing 19(2): 201-226 (2010). pdf

• Straight-line drawing of quadrangulations
  We exploit a combinatorial structure of quadrangulations to derive a simple and efficient straight-line drawing algorithm relying on face-counting operations. The procedure embeds a quadrangulation with n vertices on a regular grid with semi-perimeter n-1-Delta, where Delta is an explicit combinatorial parameter of the quadrangulation.
  • Proceedings of the 14th International Symposium on Graph Drawing (GD'06), Karlsruhe 2006, Lecture Notes In Computer Science, pages 234-239. pdf

• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics ,  with Philippe Flajolet, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne.
  In analytic combinatorics, several methods can be used to derive asymptotic estimates. In general, singularity analysis works fine when the generating function exhibits a finite number of dominant singularities, if not Darboux's method can be used provided the generating function is smooth enough. We propose here a a general approach that combines both methods. The idea is to split the generating function into two factors; the first factor contains the most dominant singularities and is treated by singularity analysis, the second factor has the same singular points as the original function, but is now smooth enough to apply Darboux's method. We describe how to effectively combine the estimates from the two factors in order to get the global asymptotic estimate. We illustrate the method on several examples related to permutations, trees, and polynomial.
  • Electronic Journal of Combinatorics, 13(1) R103, pp. 1-35 (November 2006) pdf

• Enumeration and asymptotic properties of unlabeled outerplanar graphs ,  with Manuel Bodirsky, Mihyun Kang and Stefan Vigerske
  We provide exact and asymptotic enumeration of unlabeled outerplanar graphs. As these graphs are unlabeled, they are subject to symmetries, so that the right tools to handle them are the Polya cycle index sums. Using a decomposition of outerplanar graphs by degree of connectivity, we provide expressions of the cycle index sums for outerplanar graphs, from which the coefficients can be extracted. Then, we study the singularities of the generating functions of outerplanar graphs (that can be obtained from the cycle index sums) and derive asymptotic estimates of the coefficients.
  • Electronic Journal of Combinatorics, Volume 14, R66, 2007. pdf

• Counting d-polytopes with d+3 vertices
  Polytopes with few vertices give rise to so-called Gale diagrams. In the case of d-polytopes with d+3 vertices, the Gale diagram is a configuration of points on the unit circle, that can be reduced to a regular polygon with labels satisfying some specific properties. Thus, the problem of counting d-polytopes with d+3 vertices reduces to counting such labeled polygons up to symmetries (rotations and reflections).
  • Electronic Journal of Combinatorics, Volume 13, R23, 2006. pdf

• Uniform random sampling of planar graphs in linear time
  Relying on the principles of Boltzmann samplers introduced by Duchon, Flajolet, Louchard, and Schaeffer, we propose an extremely efficient algorithm to do random generation of planar graphs. The complexity is linear if a few percents of tolerance is allowed for the size of the output. Random planar graphs with more than one million of vertices can be generated.
  • Long version, Random Structures and Algorithms 35(4): 464-522 (2009). pdf
  • Short version, under the title ``Quadratic exact-size and linear approximate-size random generation of planar graphs''. Proceedings of the AofA'05 Conference (Analysis of Algorithms-2005), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AD, pp. 125-138 (2005). pdf
  • Implementation (in java) tar.gz

• Transversal structures on triangulations: a combinatorial study and straight-line drawings
  In this article, we investigate so-called transversal structures, which characterize triangulations without non empty triangles in the same way as Schnyder Woods characterize simple triangulations. We derive from this structure a straight-line drawing algorithm of irreducible triangulations, which beats in average the best previously known drawing algorithm by a factor 27/22. As a corollary, our algorithm can also be used to have straight line drawings of 4-connected planar graphs with at least 4 outer vertices.
  • Long version, Discrete Math. Volume 309, pages 1870-1894, 2009. pdf
  • Short version, under the title "Tranversal structures on triangulations, with application to straight-line drawing". Proceedings of the 13th International Symposium on Graph Drawing (GD'05), Limerick 2005, Lecture Notes In Computer Science, pages 177-188. pdf

• Dissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling,  with Dominique Poulalhon and Gilles Schaeffer
  We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees, with interesting consequences for enumeration, mesh compression and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, and an asymptotically optimal encoding procedure.
  • Long version, Transactions on Algorithms, Volume 4 Number 2, Article 19, 2008. pdf
  • Short version. Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA'05), Vancouver 2005, SIAM press, pages 690-699. pdf

• Counting unrooted maps using tree-decomposition
  We present a new method to count unrooted maps on the sphere up to orientation-preserving homeomorphisms. The principle, called tree-decomposition, is to deform a map into an arborescent structure whose nodes are occupied by constrained maps. Tree-decomposition turns out to be very efficient and flexible for the enumeration of constrained families of maps. In this article, the method is applied to count unrooted 2-connected maps and, more importantly, to count unrooted 3-connected maps, which correspond to the combinatorial types of oriented convex polyhedra. Our method improves significantly on the previously best-known complexity to enumerate unrooted 3-connected maps.
  • Long version, Seminaire Lotharingien de Combinatoire, Volume B54A1, 44pp, 2007. pdf
  • short version (FPSAC'05) pdf
  • maple worksheet mws

Theses:

• My PhD thesis entitled "Combinatoire des cartes planaires et applications algorithmiques" (June 2007) pdf
  This thesis describes algorithms on planar maps (graphs embedded in the plane without edge-crossings) based on their combinatorial properties. For several important families of planar maps (3-connected, triangulations, quadrangulations), efficient procedures of random generation, encoding, and straight-line drawing are described. In particular, the first optimal encoder for the combinatorial incidences of polygonal meshes with spherical topology is developed. Starting from a generator for 3-connected maps, a new random generator for planar graphs is introduced. The complexity of generation is the best currently known: quadratic (in expectation) for exact-size sampling and linear (in expectation) for approximate-size sampling. Finally, several straight-line drawing algorithms for planar maps are introduced. The procedures are both simple to describe and very efficient, yielding the best known grid size for two families of maps: triangulations of the 4-gon with no filled 3-cycle ---called irreducible--- and quadrangulations. The algorithms presented in the thesis take advantage of several combinatorial structures on planar maps (orientations, partitions into spanning trees) as well as new bijective constructions.

• My Masters thesis entitled "Entrelacs, cartes et polytopes: énumération en tenant compte des symétries" (July 2003) pdf
  This report contains three rather independant parts. The first one consists of a detailed proof of the fact that the proportion of prime alternating links having a non-trivial symmetry is exponentially negligible. This proof has been integrated in the article of Sebastien Kunz-Jacques and Gilles Schaeffer on the asymptotic of the number of prime alternating links. The second part introduces the method of tree-decomposition to count unrooted maps. This part has recently been more developed and was presented at FPSAC05. The third part deals with bijections between families of trees and families of maps. Such bijections have been introduced by Gilles Schaeffer in his PHD. I use the notion of alpha-orientation to give a new version of the bijection between blossoming trees and eulerian maps. A new bijection is introduced, between a family of trees and quadrangulations without multiple edges. The proof that this is a bijection also uses the notion of alpha-orientation
  

Talks:

• Bijections on Schnyder woods (Séminaire de combinatoire Philippe Flajolet, IHP, Paris, Jan 2013) Slides
• Baxter permutations and meanders (Journées Viennot, Labri, Bordeaux, June 2012) Slides
• Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings (GD conference, Redmond, Sept 2012) Slides
• On the number of intervals in Tamari lattices (Algo Seminar, Rocquencourt, Oct. 2011) Slides
• A master bijection for planar maps, with applications (Young Workshop, Madrid, June 2011) Slides
• Exact counting formula for rooted simple bipartite maps (JCB, Bordeaux, Jan. 2011) Slides
• Dessiner un graphe dans le plan (Sieste, ENS Lyon, Nov. 2010) Slides
• Optimal encoding of triangular and quadrangular meshes of fixed topology (CCCG, Winnipeg, Aug. 2010) Slides
• Bijective counting of involutive Baxter permutations (Lattice path conference, Siena, July 2010) Slides
• On the diameter of random planar graphs (Aofa'10, Vienna, July 2010) Slides
• Pointing, asymptotics, and random generation in unlabeled classes (Algo seminar, Rocquencourt, Jan. 2010). Slides
• Distances in plane trees and planar maps (Alea, Luminy, March 2010). Slides
• Schnyder woods for higher genus triangulated surfaces (SFU discrete math seminar, Vancouver, April 2009). Slides
• Bijections for Baxter families (IHP workshop, Paris, Nov. 2009). Slides
• Asymptotic enumeration in unlabelled subcritical graph families (Canadam, Montreal, May 2009). Slides
• Bijective links on planar maps via orientations (Combinatorial Potlatch, University Puget Sound, Nov. 2008). Slides
• Decomposition and enumeration of planar graphs (UBC discrete math seminar, Vancouver, Oct. 2008). Slides
• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics (AMS fall meeting, Chicago, Oct. 2007). Slides
• Bijective counting of plane bipolar orientations (Eurocomb, Sevilla, Sept. 2007). Slides
• Transversal structures on triangulations, with application to straight line drawing (GD conference, Limerick Sept 2005). Slides
• A linear time algorithm for the random generation of labeled planar graphs.  Seminar Humboldt University (Berlin) Dec 2005   Slides
• Straight-line drawing of quadrangulations (GD conference, Karlsruhe, Sept 2006). Slides
• Estimating the number of Active Flows in a Data Stream over a Sliding Window (SODA conference, New Orleans, Jan 2007). Slides
• Random generation of combinatorial structures using Boltzmann samplers (Berlin, July 2007). Slides
• Counting unrooted maps using tree-decomposition (Algo seminar, Rocquencourt, Oct 2004). Slides
• A bijection between binary trees and some dissections.  (SLC, Ellwangen, 2004)   Slides
• PhD thesis presentation Slides
  
• Masters thesis presentation Slides
  

Teaching: