Olivier Bernardi
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
Research Interests
Olivier Bernardi has a total of 31 co-authors. Here are the top co-authors by number of shared publications:
- Éric Fusy
LIGM, CNRS, Univ. Gustave Eiffel
12 shared publications Guillaume Chapuy
4 shared publications- Shizhe Liang
Department of Mathematics Brandeis University Waltham MA USA
3 shared publications Éric Fusy
3 shared publicationsAlejandro H. Morales
2 shared publications- Alejandro H. Morales
Department of Mathematics, Massachusetts Institute of Technology; Cambridge, MAUSA02139
2 shared publications
Latest Publications
- Open Access
- 11 March 2025
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 29 (1) , 187-246
A Census of Graph-Drawing Algorithms Based on Generalized Transversal Structures
We present two graph drawing algorithms based on the recently defined "grand-Schnyder woods", which are a far-reaching generalization of the classical Schnyder woods. The first is a straight-line drawing algorithm for plane graphs with faces of degree 3 and 4 with no separating 3-cycle, while the second is a rectangular drawing algorithm for the dual of such plane graphs.In our algorithms, the coordinates of the vertices are defined in a global manner, based on the underlying grand-Schnyder woods. The grand-Schnyder woods and drawings are computed in linear time. When specializing our algorithms to special classes of plane graphs, we recover the following known algorithms: (1) He's algorithm for rectangular drawing of 3-valent plane graphs, based on transversal structures, (2) Fusy's algorithm for the straight-line drawing of triangulations of the square, based on transversal structures, (3) Bernardi and Fusy's algorithm for the orthogonal drawing of 4-valent plane graphs, based on 2-orientations, (4) Barriere and Huemer's algorithm for the straight-line drawing of quadrangulations, based on separating decompositions. Our contributions therefore provide a unifying perspective on a large family of graph drawing algorithms that were originally defined on different classes of plane graphs and were based on seemingly different combinatorial structures.
- 11 March 2025
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 29 (1) , 187-246
Open AccessA Census of Graph-Drawing Algorithms Based on Generalized Transversal Structures
We present two graph drawing algorithms based on the recently defined "grand-Schnyder woods", which are a far-reaching generalization of the classical Schnyder woods. The first is a straight-line drawing algorithm for plane graphs with faces of degree 3 and 4 with no separating 3-cycle, while the second is a rectangular drawing algorithm for the dual of such plane graphs.In our algorithms, the coordinates of the vertices are defined in a global manner, based on the underlying grand-Schnyder woods. The grand-Schnyder woods and drawings are computed in linear time. When specializing our algorithms to special classes of plane graphs, we recover the following known algorithms: (1) He's algorithm for rectangular drawing of 3-valent plane graphs, based on transversal structures, (2) Fusy's algorithm for the straight-line drawing of triangulations of the square, based on transversal structures, (3) Bernardi and Fusy's algorithm for the orthogonal drawing of 4-valent plane graphs, based on 2-orientations, (4) Barriere and Huemer's algorithm for the straight-line drawing of quadrangulations, based on separating decompositions. Our contributions therefore provide a unifying perspective on a large family of graph drawing algorithms that were originally defined on different classes of plane graphs and were based on seemingly different combinatorial structures.
- Open Access
Bijections for faces of braid-type arrangements
We establish a general bijective framework for encoding faces of some classical hyperplane arrangements. Precisely, we consider hyperplane arrangements in $\mathbb{R}^n$ whose hyperplanes are all of the form $\{x_i-x_j=s\}$ for some $i,j\in[n]$ and $s\in \mathbb{Z}$. Such an arrangement $A$ is \emph{strongly transitive} if it satisfies the following condition: if $\{x_i-x_j=s\}\notin A$ and $\{x_j-x_k=t\}\notin A$ for some $i,j,k\in [n]$ and $s,t\geq 0$, then $\{x_i-x_k=s+t\}\notin A$. For any strongly transitive arrangement $A$, we establish a bijection between the faces of $A$ and some set of decorated plane trees.Open AccessBijections for faces of braid-type arrangements
We establish a general bijective framework for encoding faces of some classical hyperplane arrangements. Precisely, we consider hyperplane arrangements in $\mathbb{R}^n$ whose hyperplanes are all of the form $\{x_i-x_j=s\}$ for some $i,j\in[n]$ and $s\in \mathbb{Z}$. Such an arrangement $A$ is \emph{strongly transitive} if it satisfies the following condition: if $\{x_i-x_j=s\}\notin A$ and $\{x_j-x_k=t\}\notin A$ for some $i,j,k\in [n]$ and $s,t\geq 0$, then $\{x_i-x_k=s+t\}\notin A$. For any strongly transitive arrangement $A$, we establish a bijection between the faces of $A$ and some set of decorated plane trees. - 14 November 2024
- Published by Springer Nature in Annals of Combinatorics
- Vol. 29 (2) , 273-373
Grand-Schnyder Woods
- 14 November 2024
- Published by Springer Nature in Annals of Combinatorics
- Vol. 29 (2) , 273-373
Grand-Schnyder Woods
- 12 October 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (1)
Tutte polynomials for regular oriented matroids
- 12 October 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (1)
Tutte polynomials for regular oriented matroids
- Open Access
A Schnyder-type drawing algorithm for 5-connected triangulations
We define some Schnyder-type combinatorial structures on a class of planar triangulations of the pentagon which are closely related to 5-connected triangulations. The combinatorial structures have three incarnations defined in terms of orientations, corner-labelings, and woods respectively. The wood incarnation consists in 5 spanning trees crossing each other in an orderly fashion. Similarly as for Schnyder woods on triangulations, it induces, for each vertex, a partition of the inner triangles into face-connected regions (5~regions here). We show that the induced barycentric vertex-placement, where each vertex is at the barycenter of the 5 outer vertices with weights given by the number of faces in each region, yields a planar straight-line drawing.
Open AccessA Schnyder-type drawing algorithm for 5-connected triangulations
We define some Schnyder-type combinatorial structures on a class of planar triangulations of the pentagon which are closely related to 5-connected triangulations. The combinatorial structures have three incarnations defined in terms of orientations, corner-labelings, and woods respectively. The wood incarnation consists in 5 spanning trees crossing each other in an orderly fashion. Similarly as for Schnyder woods on triangulations, it induces, for each vertex, a partition of the inner triangles into face-connected regions (5~regions here). We show that the induced barycentric vertex-placement, where each vertex is at the barycenter of the 5 outer vertices with weights given by the number of faces in each region, yields a planar straight-line drawing.
- 1 January 2023
- Published by Springer Nature
- p. 117-132
A Schnyder-Type Drawing Algorithm for 5-Connected Triangulations
- 1 January 2023
- Published by Springer Nature
- p. 117-132
A Schnyder-Type Drawing Algorithm for 5-Connected Triangulations
- Top Cited PapersOpen Access
- 9 December 2021
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 1
Counting quadrant walks via Tutte's invariant method
In the 1970s, William Tutte developed a clever algebraic approach, based on certain "invariants", to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past 20 years to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in $\{-1, 0,1\}^2$. We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically. Then, we move to a complex analytic viewpoint that has already proved very powerful, leading in particular to integral expressions for the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions for the generating function, and a proof that this series is D-algebraic (that is, satisfies polynomial differential equations). Keywords: Lattice walks, enumeration, differentially algebraic series, conformal mappings. Mathematics Subject Classifications: 05A15, 34K06, 39A06, 30C20, 30D05- 9 December 2021
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 1
Top Cited PapersOpen AccessCounting quadrant walks via Tutte's invariant method
In the 1970s, William Tutte developed a clever algebraic approach, based on certain "invariants", to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past 20 years to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in $\{-1, 0,1\}^2$. We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically. Then, we move to a complex analytic viewpoint that has already proved very powerful, leading in particular to integral expressions for the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions for the generating function, and a proof that this series is D-algebraic (that is, satisfies polynomial differential equations). Keywords: Lattice walks, enumeration, differentially algebraic series, conformal mappings. Mathematics Subject Classifications: 05A15, 34K06, 39A06, 30C20, 30D05 - 1 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 343 (10)
Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
- 1 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 343 (10)
Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
- Open Access
Universal Tutte polynomial
The Tutte polynomial is a well-studied invariant of graphs and matroids. We first extend the Tutte polynomial from graphs to hypergraphs, and more generally from matroids to polymatroids, as a two-variable polynomial. Our definition is related to previous works of Cameron and Fink and of K\'alm\'an and Postnikov. We then define the universal Tutte polynomial $\T_n$, which is a polynomial of degree $n$ in $2+(2^n-1)$ variables that specializes to the Tutte polynomials of all polymatroids (hence all matroids) on a ground set with $n$ elements. The universal polynomial $\T_n$ admits three kinds of symmetries: translation invariance, $S_n$-invariance, and duality.Open AccessUniversal Tutte polynomial
The Tutte polynomial is a well-studied invariant of graphs and matroids. We first extend the Tutte polynomial from graphs to hypergraphs, and more generally from matroids to polymatroids, as a two-variable polynomial. Our definition is related to previous works of Cameron and Fink and of K\'alm\'an and Postnikov. We then define the universal Tutte polynomial $\T_n$, which is a polynomial of degree $n$ in $2+(2^n-1)$ variables that specializes to the Tutte polynomials of all polymatroids (hence all matroids) on a ground set with $n$ elements. The universal polynomial $\T_n$ admits three kinds of symmetries: translation invariance, $S_n$-invariance, and duality. - Open Access
- 24 February 2020
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 7 (1) , 75-164
Unified bijections for planar hypermaps with general cycle-length constraints
- 24 February 2020
- Published by European Mathematical Society - EMS - Publishing House GmbH in Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions
- Vol. 7 (1) , 75-164
Open AccessUnified bijections for planar hypermaps with general cycle-length constraints