7 citations · 17 across the 11 of their papers we have counts for
14 papers
Freeze-Tag with Return
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse +3
In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awak…
Higher dimensional floorplans and Baxter d-permutations
Nicolas Bonichon, Thomas Muller, Adrian Tanasa
A dimensional mosaic floorplan is a partition of a rectangle by other rectangles with no empty rooms. These partitions (considered up to some deformations) are known to be in b…
Freeze-Tag in has Wake-up Time Five
Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille +1
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of robots, starting from a single active robot. In the basic geometric version, every…
Baxter -permutations and other pattern avoiding classes
Nicolas Bonichon, Pierre-Jean Morel
A permutation of size can be identified to its diagram in which there is exactly one point per row and column in the grid . In this paper we consider multidimensional pe…
Gallai's path decomposition in planar graphs
Alexandre Blanché, Marthe Bonamy, Nicolas Bonichon
In 1968, Gallai conjectured that the edges of any connected graph with vertices can be partitioned into paths. We show that this conjecture is true…
A bijection for essentially 3-connected toroidal maps
Nicolas Bonichon, Éric Fusy, Benjamin Lévêque
We present a bijection for toroidal maps that are essentially -connected (-connected in the periodic planar representation). Our construction actually proceeds on certain clo…
A bijection for essentially 4-connected toroidal triangulations
Nicolas Bonichon, Benjamin Lévêque
Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have bee…
On the number of planar Eulerian orientations
Nicolas Bonichon, Mireille Bousquet-Mélou, Paul Dorbec +1
The number of planar Eulerian maps with n edges is well-known to have a simple expression. But what is the number of planar Eulerian orientations with n edges? This problem appears…
Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
Nicolas Bonichon, Prosenjit Bose, Paz Carmi +3
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is - and -monotone. Angle-monotone graphs are -spa…
Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations
Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel +2
Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routi…
There are Plane Spanners of Maximum Degree 4
Nicolas Bonichon, Iyad Kanj, Ljubomir Perković +1
Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner,…
The Stretch Factor of - and -Delaunay Triangulations
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse +1
In this paper we determine the stretch factor of the -Delaunay and -Delaunay triangulations, and we show that this stretch is . Betw…
Baxter permutations and plane bipolar orientations
Nicolas Bonichon, Mireille Bousquet-Mélou, Eric Fusy
We present a simple bijection between Baxter permutations of size and plane bipolar orientations with n edges. This bijection translates several classical parameters of permuta…
Catalan's intervals and realizers of triangulations
Olivier Bernardi, Nicolas Bonichon
The Stanley lattice, Tamari lattice and Kreweras lattice are three remarkable orders defined on the set of Catalan objects of a given size. These lattices are ordered by inclusion:…