Schnyder Woods for Higher Genus Triangulated Surfaces ∗ (2009)
Luca Castelli Aleardi, Éric Fusy, Thomas Lewiner
Schnyder woods are a well known combinatorial structure for planar graphs, which yields a decomposition into 3 vertexspanning trees. Our goal is to extend definitions and algorithms for Schnyder...
Abstract Boltzmann Sampling of Unlabelled Structures (2008)
Boltzmann models from statistical physics combined with methods from analytic combinatorics give rise to efficient algorithms for the random generation of unlabelled objects. The resulting algorithms...
A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components (2008)
Éric Fusy, Mihyun Kang, Bilyana Shoilekova
Abstract. We develop a general methodology to enumerate families of graphs. To this aim we write down a generic grammar to decompose a graph family into 3-connected components, thereby reducing the...
BIJECTIVE COUNTING OF PLANE BIPOLAR ORIENTATIONS (2008)
Éric Fusy, Dominique Poulalhon, Gilles Schaeffer
Abstract. We introduce a bijection between plane bipolar orientations with fixed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with some specific extremities....
Extended abstract submitted to ICALP’06. BOLTZMANN SAMPLING OF UNLABELLED STRUCTURES (2008)
Philippe Flajolet, Éric Fusy, Carine Pivoteau
Abstract. Boltzmann models from statistical physics combined with methods from analytic combinatorics give rise to efficient algorithms for the random generation of unlabelled objects. The resulting...
3.3. Algorithms on Sequences 3 (2008)
Bruno Salvy [dr, Virginie Collette [tr, Alin Bostan [cr, Frédéric Chyzak [cr, Mireille Régnier [dr, Julien Fayolle, ...
c t i v it y
Bijections for Baxter Families and Related Objects (2008)
Felsner, Stefan, Fusy, Éric, Noy, Marc, Orden, David
The Baxter number can be written as $B_n = \sum_0^n \Theta_{k,n-k-1}$. These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter...
Abstract Boltzmann Sampling of Unlabelled Structures (2008)
Boltzmann models from statistical physics combined with methods from analytic combinatorics give rise to efficient algorithms for the random generation of unlabelled objects. The resulting algorithms...
Counting D-Polytopes With D + 3 Vertices (2008)
Eric Fusy Algorithm, Éric Fusy
We completely solve the problem of enumerating combinatorially inequivalent d-dimensional polytopes with d + 3 vertices. A first solution of this problem, by Lloyd, was published in 1970. But the...
Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm (2007)
Éric Fusy, Olivier G, Frédéric Meunier
This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG, dedicated to estimating the number of distinct elements (the cardinality) of very large data...
Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs, in "Electronic (2007)
Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske, Projet Algo, Inria Rocquencourt
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number gn of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and gn is...
Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm (2007)
This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG, dedicated to estimating the number of distinct elements (the cardinality) of very large data...
Straight-line drawing of quadrangulations (2006)
Abstract. This article introduces a straight-line drawing algorithm for quadrangulations, in the family of the face-counting algorithms. It outputs in linear time a drawing on a regular W ×H grid...
Abstract. We define and study a structure called transversal edgepartition related to triangulations without non empty triangles, which is equivalent to the regular edge labeling discovered by Kant...
Quadratic exact-size and linear approximate-size random sampling of planar graphs (2005)
This extended abstract introduces a new algorithm for the random generation of labelled planar graphs. Its principles rely on Boltzmann samplers as recently developed by Duchon, Flajolet, Louchard,...
ITU-T Recommendation H.263 Version 2 (H.263+), Video coding for low bitrate communication (1998)
This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, called irreducible triangulations. The structure has...
Bijections for Baxter Families and Related Objects
Stefan Felsner, Marc Noy, Departament Matemàtica, Aplicada Ii, Éric Fusy, ...
The Baxter number Bn can be written as Bn = � n 0 Θk,n−k−1 with Θk,ℓ = 2 (k + 1) 2 (k + 2)