Eric Fusy
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Eric Fusy has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Daniel Panario
Carleton University
2 shared publications - Nicolas Pouyanne
Université de Versailles - St-Quentin
2 shared publications - Philippe Flajolet
INRIA
2 shared publications - Xavier Gourdon
Algorithms Project and Dassault Systems France
2 shared publications Manuel Bodirsky
Institut für Informatik Unter Humboldt-Universität zu Berlin 10099 Linden 6 Berlin Germany
1 shared publicationMihyun Kang
Institut für Informatik Unter Humboldt-Universität zu Berlin 10099 Linden 6 Berlin Germany
1 shared publication
Latest Publications
- 23 June 2009
- Published by Wiley in Random Structures & Algorithms
- Vol. 35 (4) , 464-522
Uniform random sampling of planar graphs in linear time
This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon, and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost; and the expected time complexity of generation is quadratic for exact‐size uniform sampling and linear for uniform approximate‐size sampling. This greatly improves on the best previously known time complexity for exact‐size uniform sampling of planar graphs with n vertices, which was a little over O(n7). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009
- 23 June 2009
- Published by Wiley in Random Structures & Algorithms
- Vol. 35 (4) , 464-522
Uniform random sampling of planar graphs in linear time
This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon, and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost; and the expected time complexity of generation is quadratic for exact‐size uniform sampling and linear for uniform approximate‐size sampling. This greatly improves on the best previously known time complexity for exact‐size uniform sampling of planar graphs with n vertices, which was a little over O(n7). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009
- Open Access
Uniform random sampling of planar graphs in linear time
This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Gim\'enez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost. Then, the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with $n$ vertices, which was a little over $O(n^7)$.Open AccessUniform random sampling of planar graphs in linear time
This article introduces new algorithms for the uniform random generation of labelled planar graphs. Its principles rely on Boltzmann samplers, as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a suitable use of rejection, a new combinatorial bijection found by Fusy, Poulalhon and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Gim\'enez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost. Then, the expected time complexity of generation is quadratic for exact-size uniform sampling and linear for approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with $n$ vertices, which was a little over $O(n^7)$. - Open Access
Baxter permutations and plane bipolar orientations
We present a simple bijection between Baxter permutations of size $n$ and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations (number of ascents, right-to-left maxima, left-to-right minima...) into natural parameters of plane bipolar orientations (number of vertices, degree of the sink, degree of the source...), and has remarkable symmetry properties. By specializing it to Baxter permutations avoiding the pattern 2413, we obtain a bijection with non-separable planar maps. A further specialization yields a bijection between permutations avoiding 2413 and 3142 and series-parallel maps.Open AccessBaxter permutations and plane bipolar orientations
We present a simple bijection between Baxter permutations of size $n$ and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations (number of ascents, right-to-left maxima, left-to-right minima...) into natural parameters of plane bipolar orientations (number of vertices, degree of the sink, degree of the source...), and has remarkable symmetry properties. By specializing it to Baxter permutations avoiding the pattern 2413, we obtain a bijection with non-separable planar maps. A further specialization yields a bijection between permutations avoiding 2413 and 3142 and series-parallel maps. - Open Access
Transversal structures on triangulations: a combinatorial study and straight-line drawings
This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, which are called irreducible triangulations. The structure has been introduced by Xin He under the name of regular edge-labelling and consists of two bipolar orientations that are transversal. For this reason, the terminology used here is that of transversal structures. The main results obtained in the article are a bijection between irreducible triangulations and ternary trees, and a straight-line drawing algorithm for irreducible triangulations. For a random irreducible triangulation with $n$ vertices, the grid size of the drawing is asymptotically with high probability $11n/27\times 11n/27$ up to an additive error of $\cO(\sqrt{n})$. In contrast, the best previously known algorithm for these triangulations only guarantees a grid size $(\lceil n/2\rceil -1)\times \lfloor n/2\rfloor$.Open AccessTransversal structures on triangulations: a combinatorial study and straight-line drawings
This article focuses on a combinatorial structure specific to triangulated plane graphs with quadrangular outer face and no separating triangle, which are called irreducible triangulations. The structure has been introduced by Xin He under the name of regular edge-labelling and consists of two bipolar orientations that are transversal. For this reason, the terminology used here is that of transversal structures. The main results obtained in the article are a bijection between irreducible triangulations and ternary trees, and a straight-line drawing algorithm for irreducible triangulations. For a random irreducible triangulation with $n$ vertices, the grid size of the drawing is asymptotically with high probability $11n/27\times 11n/27$ up to an additive error of $\cO(\sqrt{n})$. In contrast, the best previously known algorithm for these triangulations only guarantees a grid size $(\lceil n/2\rceil -1)\times \lfloor n/2\rfloor$. - Open Access
A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
A ``hybrid method'', dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions--this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.
Open AccessA Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
A ``hybrid method'', dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions--this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.
- Open Access
Enumeration of Unlabeled Outerplanar Graphs
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and g_n is asymptotically $g n^{-5/2}\rho^{-n}$, where $g\approx0.00909941$ and $\rho^{-1}\approx7.50360$ can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on n vertices, for instance concerning connectedness, chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics.Open AccessEnumeration of Unlabeled Outerplanar Graphs
We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and g_n is asymptotically $g n^{-5/2}\rho^{-n}$, where $g\approx0.00909941$ and $\rho^{-1}\approx7.50360$ can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on n vertices, for instance concerning connectedness, chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics. - Open Access
- 7 January 2006
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R103
A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
A "hybrid method", dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions—this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.
- 7 January 2006
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R103
Open AccessA Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
A "hybrid method", dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions—this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.
- Open Access
- 7 January 2006
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R23
Counting $d$-Polytopes with $d+3$ VerticesWe 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 obtained counting formula was not correct, as pointed out in the new edition of Grünbaum's book. We both correct the mistake of Lloyd and propose a more detailed and self-contained solution, relying on similar preliminaries but using then a different enumeration method involving automata. In addition, we introduce and solve the problem of counting oriented and achiral (i.e., stable under reflection) $d$-polytopes with $d+3$ vertices. The complexity of computing tables of coefficients of a given size is then analyzed. Finally, we derive precise asymptotic formulas for the numbers of $d$-polytopes, oriented $d$-polytopes and achiral $d$-polytopes with $d+3$ vertices. This refines a first asymptotic estimate given by Perles.- 7 January 2006
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R23
Open AccessCounting $d$-Polytopes with $d+3$ VerticesWe 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 obtained counting formula was not correct, as pointed out in the new edition of Grünbaum's book. We both correct the mistake of Lloyd and propose a more detailed and self-contained solution, relying on similar preliminaries but using then a different enumeration method involving automata. In addition, we introduce and solve the problem of counting oriented and achiral (i.e., stable under reflection) $d$-polytopes with $d+3$ vertices. The complexity of computing tables of coefficients of a given size is then analyzed. Finally, we derive precise asymptotic formulas for the numbers of $d$-polytopes, oriented $d$-polytopes and achiral $d$-polytopes with $d+3$ vertices. This refines a first asymptotic estimate given by Perles. - Open Access
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.
Open AccessCounting 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.
- Open Access
Counting d-polytopes with d+3 vertices
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 obtained counting formula was not correct, as pointed out in the new edition of Gr\"unbaum's book. We both correct the mistake of Lloyd and propose a more detailed and self-contained solution, relying on similar preliminaries but using then a different enumeration method involving automata. In addition, we introduce and solve the problem of counting oriented and achiral (i.e. stable under reflection) $d$-polytopes with $d+3$ vertices. The complexity of computing tables of coefficients of a given size is then analyzed. Finally, we derive precise asymptotic formulas for the numbers of $d$-polytopes, oriented $d$-polytopes and achiral $d$-polytopes with $d+3$ vertices. This refines a first asymptotic estimate given by Perles.Open AccessCounting d-polytopes with d+3 vertices
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 obtained counting formula was not correct, as pointed out in the new edition of Gr\"unbaum's book. We both correct the mistake of Lloyd and propose a more detailed and self-contained solution, relying on similar preliminaries but using then a different enumeration method involving automata. In addition, we introduce and solve the problem of counting oriented and achiral (i.e. stable under reflection) $d$-polytopes with $d+3$ vertices. The complexity of computing tables of coefficients of a given size is then analyzed. Finally, we derive precise asymptotic formulas for the numbers of $d$-polytopes, oriented $d$-polytopes and achiral $d$-polytopes with $d+3$ vertices. This refines a first asymptotic estimate given by Perles.