Éric Fusy's Home Page

Éric Fusy

I am a CNRS researcher at LIX, Ecole Polytechnique. My fields of research are enumerative combinatorics, random generation, graph drawing, and probabilistic algorithms.

Articles and Preprints:

• 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.
  • Submitted to Journal of Algebra (Computational). 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.
  • short version, SoCG'08 pdf
  • long version, to appear in Discrete and Computational Geometry pdf

• Baxter permutations and plane bipolar orientations,   with Nicolas Bonichon and Mireille Bousquet Melou
  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.
  • Submitted arxiv

• 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.
  • Submitted 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. We recover in this way several recent results on the enumeration of families of planar graphs; in particular the 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 very 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
  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.
  • Short version, FPSAC'08 pdf
  • Long version, to appear in European Journal of Combinatorics pdf

• Bijective counting of plane bipolar orientations,  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.
  • Short version, Eurocomb'07 pdf
  • Long version, to appear in European Journal of Combinatorics pdf

• HyperLogLog, the analysis of a near-optimal cardinality estimation algotithm,  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.
  • AofA'07 pdf

• An unbiased pointing operator for unlabeled structures, with applications to counting and sampling,  with Manuel Bodirsky, Mihyun Kang and Stefan Vigerske
  A very fruitful approach to enumerate a class of labeled structures (e.g. unrooted trees) is to consider instead the associated rooted class. The rooted class is easier to count because the root gives a starting point for a recursive decomposition. Then the n-th counting coefficient of the unrooted class is equal to the n-th coefficient of the rooted class divided by n (because a structure of size n gives rise to n rooted structures). In the unlabeled setting, the pointing approach does not adapt straightforwardly, because a structure of size n can give rise to less than n pointed structures (because rooting at two vertices in symmetric position gives the same rooted object). In this article, we solve this problem by introducing a pointing operator such that each unlabeled unrooted structure of size n gives rise to n unlabeled pointed structures. To this aim, we have to point not only a vertex but a symmetric cycle of vertices. We illustrate how this approach can be applied to enumerate several families of unlabeled structures and to obtain efficient random generators on such classes.
  • SODA'07 pdf

• Estimating the number of Active Flows in a Data Stream over a Sliding Window ,  with Frederic Giroire
  How can we efficiently extract informations from huge data sets using only a constant auxiliary memory? The idea is to relax the constraint of returning an exact value of the parameter. In practice, it is sufficient to compute an estimate that has 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) to work over a sliding window. We 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.
  • ANALCO'07 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, ...
  • ANALCO'07 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).
  • short version, GASCOM'06 pdf
  • long version, to appear in Combinatorics, Probability and Computing 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.
  • GraphDrawing'06 pdf

• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics ,  with Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario, Nicolas Pouyanne.
  In analytic combinatorics, there are several methods to derive asymptotic estimates, which are applied in different contexts. In general, singularity analysis works fine when the generating function exhibits a finite number of dominant singularities. When it is not the case, Darboux's method can be used provided the generating function is smooth enough. We propose here a general method that combines both frameworks. 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.
  • short version (published in AofA'05 under the name ``Quadratic exact-size and linear approximate-size random generation of planar graphs'') ps pdf
  • long version, to appear in Random Structures and Algorithms. 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 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.
• short version (GraphDrawing'05) ps pdf
• long version, Discrete Math. Volume 309, pages 1870-1894, 2009. pdf

• Dissections and trees, with applications to optimal mesh encoding and to random sampling ,  with Dominique Poulalhon and Gilles Schaeffer
  • short version (SODA'05) ps pdf
  • long version, Transactions on Algorithms, Volume 4 Number 2, Article 19, 2008. ps pdf

• Counting unrooted maps using tree-decomposition
  • short version (FPSAC'05) ps pdf
  • long version, Seminaire Lotharingien de Combinatoire, Volume B54A1, 2007.
  • 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) ps 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 :

• Schnyder woods for higher genus triangulated surfaces (SFU, Vancouver, April 2009). Slides
• Bijective links on planar maps via orientations (University Puget Sound, Nov. 2008). Slides
• Decomposition and enumeration of planar graphs (UBC, Vancouver, Oct. 2008). Slides
• A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics (Chicago, Oct. 2007). Slides
• Bijective counting of plane bipolar orientations (Sevilla, Sept. 2007). Slides
• An unbiased pointing operator for unlabeled structures (Montreal, Feb 2007). Slides
• Transversal structures on triangulations, with application to straight line drawing (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 (Karlsruhe, Sept 2006). Slides
• Estimating the number of Active Flows in a Data Stream over a Sliding Window (New Orleans, Jan 2007). Slides
• Random generation of combinatorial structures using Boltzmann samplers (Berlin, July 2007). Slides
• Counting unrooted maps using tree-decomposition (Oct 2004). Slides
• A bijection between binary trees and some dissections. Séminaire lotharingien 2004 (Ellwangen)   Slides  
  
• PhD thesis presentation Slides
  
• Masters thesis presentation Slides