Leo Senique

Carlos Canudas-De-Wit
email: carlos.canudas-de-wit@gipsa-lab.fr

GTL-Rocade: Experimental platform for real-time traffic modeling, prediction and control

Keywords: Travel time prediction, traffic data, pollutants estimation, Grenoble South ring 1

Developed with the support of the ERC Scale-FreeBack, GTL-Rocade is an experimental platform for collecting real-time traffic data from a network of wireless sensors installed on the southern bypass of Grenoble. The objective of GTL-Rocade is to collect traffic data and compute traffic indicators in real time. This data is intended to test new traffic prediction algorithms, validate mathematical traffic models, and evaluate real-time traffic statistics.

Introduction

Urban traffic represents one of the biggest challenges in most large cities, which directly impacts economic, health, and societal issues. To address this issue, Intelligent Transportation Systems (ITS) have been recently proposed to provide innovate services and tools that enable users to be better informed, and that allow traffic operators to make more coordinated, targeted and effective decisions for the management and scheduling of vehicles. Thus, ITS benefit greatly on research regarding the modeling, monitoring, and control of traffic networks. A large research community is focused on the study of vehicular traffic, in particular on the case of highways and motorways. In this paper, we present and describe the GTL-Rocade experimental platform, which can be accessed at the following link: http://gtl.inrialpes.fr . The objective of GTL-Rocade is to collect traffic data, compute traffic indicators in real time and calculate traffic predictions. This data is intended to test new traffic prediction algorithms, validate mathematical traffic models, and evaluate real-time traffic statistics. This platform is part of the Grenoble Traffic Lab (GTL), which considers the city of Grenoble in France as a case study. This work is developed in the context of the European Research Council (ERC) grant project Scale-FreeBack. The structure of this paper is the following: Section 2 presents an overview of the structure of the platform. Section 3 goes over the methods and models used for the indicators used in the application, based on the work of the research team. Section 4 describes the sensors used to retrieve the input data, and the calibration of that data. Section 5 details the user interface and features available on the platform, and how users can operate them. Finally, section 6 concludes the paper.

Platform overview

The architecture of GTL-Rocade is divided in 3 levels (see figure 1): the physical level, the data processing level, and the display level.  The physical level (level 1) is comprised of 130 magneto-resistive sensors located on 10.5 km of a two-way highway. They are distributed over 26 data collection points and provide information on several macroscopic metrics: flow, speed and occupancy.  The data processing level (level 2) consists of an upper and lower layer.

• The upper layer takes the raw macroscopic traffic data from the magnetometers and stores them in a database. They are then passed through a series of signalprocessing algorithms which perform imputations for missing or wrong data, aggregate data to reduce noise and calibrate the model for traffic-density estimation. • The lower layer uses the pre-processed data to compute several traffic indicators.

These are calculated both for the current real-time data and for predictions.  The display level (level 3) uses the indicators computed in level 2 to provide a visualization. At the current moment this only includes the web interface, as the mobile app and the showroom are deprecated.

Both input data and processed data are stored on a MariaDB database set up on an external physical server.

We give a more detailed description of each level in the following sections. The fuel consumption and CO2 emissions are estimated using a physics-based modal consumption model [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF] for a Diesel-powered vehicle while for the NOx emissions we relied on the statistical model proposed in a 2006 paper [START_REF] Int Panis | Modelling instantaneous traffic emission and the influence of traffic speed limits[END_REF]. Finally, the safety index is computed according to a constant time-headway spacing policy with a nominal time headway of two seconds as a reference [START_REF] Martinez | A safe longitudinal control for adaptive cruise control and stop-and-go scenarios[END_REF]. This is based on the "two second distance rule" that tells a driver the minimum distance needed to reduce the risk of collision with the vehicle directly in front, under ideal driving conditions: two seconds is a safety buffer, and the rule attempts to respect a distance which is consistent with human reaction time (approximately 1.5-2 s).

Prediction

In order to forecast travel time within the highway, we use the measurements describing travel times for the different origin-destination (OD) pairs. A network model is then used to infer travel time between origin and destination based on a reduced number of states. The forecast strategy is based on both current day and historical data. Historical data is organized into several clusters; for each cluster, a predictor is designed based on the Kalman filtering strategy. Then a fusion algorithm, described in [START_REF] Lopez | Travel time forecasting from clustered time series via optimal fusion strategy[END_REF], is used in order to merge the predictions. Applied over traffic data from the South ring of Grenoble, the error is guaranteed to be less or equal than 35% in 90% of the cases.

Calibration and input data

Implemented in collaboration with local traffic authorities (DIR-CE), GTL Rocade consists of 130 magneto-resistive sensors located on 10.5 km of a two-way highway. They are distributed over 26 data collection points at 20 locations and provide information on several macroscopic metrics: flow, speed and occupancy (the fraction of time during which the cross-section is occupied by a vehicle). Microscopic information is also provided, such as single-vehicle speed, inter-vehicle gap and vehicle length.

The sensors, buried in the Grenoble south ring under the pavement, are magnetic and wireless, with a lifespan of 10 years; self-calibrated, they can be remotely managed from a central console. Their data are received by access points, whose range can be extended by repeaters. Access point are used to maintain two-way communications with sensors and battery-powered repeaters; using either wired and/or wireless connections, access points relay data to road-side controllers, remote servers, traffic management systems, or other vehicle detection applications.

Figure 2: Sensys Networks VDS240 magnetometer

Every 15 seconds, raw data is stored on the database and passed through of series of signalprocessing algorithms which perform:  Imputation and diagnostics: if some data are lost or erroneous (for instance, as a result of communication problems or temporary sensor malfunction), suitable imputation algorithms [START_REF] Smith | Exploring Imputation Techniques for Missing Data in Transportation Management Systems[END_REF], [START_REF] Muralidharan | Imputation of Ramp Flow Data for Freeway Traffic Simulation[END_REF] are run for filling in the missing data with estimated values.  Aggregation: high-resolution traffic data tend to be noisy. In order to capture dynamics that are physically meaningful, it is then fundamental to aggregate the data into time slots of 1, 5 or 6 minutes, depending on the scenario under investigation.  Model calibration: model-based algorithms are used for computing the traffic indicators. The parameters of the fluid-dynamic models are automatically estimated from the data.

User interface

The platform's web interface features several tabs at the top:  The Status tab displays the different indicators for each section of road and each moment of the day. It shows sensor data such as average speed, but also data calculated in real time. These include the travel time across the bypass, the number of vehicles, the length of any congestion and the CO2 and NOx emissions.  A Predictions tab, providing travel time predictions along the bypass, is also available.

The user can select an entry point and an exit point of the road to see the travel time given the departure time, calculated from prediction algorithms using sensor data.  On the Pmv tab, it is also possible to get information about the traffic on the highway in the form of variable-message sign. By clicking on the desired entry point, you can see the current travel time and the traffic flow.  The Statistics tab allows you to consult the state of the network measured and calculated for the previous days using the data stored in the database. The evolution of different indicators over a chosen period (day, week or month) can be displayed in the form of graphs and histograms.  The Data Quality tab provides information on the status of the sensors. It shows in details the information available for each sensor and their evolution over a chosen period.  On the Data Download tab, users have the option to submit a download request for the selected raw or imputed data. Creating an account is required to make this request.

Status module

Shown on figure 3 is the interface for the status tab. It is divided into 3 parts.

On the left panel, a heat map shows the value of the selected indicator for each section of the road (21 in total, from East to West) over time. It shows the average speed for the current day by default, but you can select a different day or a different indicator above the histogram.

In the upper panel, several bars show the current average value of each indicator for each sector.

There is a map on the right panel to show the level of the selected indicator on the highway, with the same color map as the histogram.

If you hover over a point on the heat map, you can see the exact value for that section and that time. It will also show you on the map where the section is located and update the displays accordingly.

Prediction module

Shown on figure 4 is the interface for the prediction module To display a prediction go into the left panel and determine one origin and one destination by selecting in the dropdown menu or click on the bullets located in the right hand side of the map (blue for inputs, red for outputs). Then then a time of departure or time of arrival and select a particular time. Finally click on Go to obtain the data. Computations are based in measurements taken up to the actual time and the travel time is predicted in a future horizon of 45mins. Once data is collected, (past days) the dynamic travel time is computed based on the real measurements taken in the highway. The two curves can be distinguished as red (predictions) and blue (real).

Once the system performs the prediction in addition a recommendation system selects the best and worst options for the predicted travel time. The optimal departure time is displayed with a green color bar and the optimal departure time is shown in the left part of the bar. The longest time trip is displayed in red.

Statistics module

The statistics module shows the statistics for each indicator over a selected period of time. It is divided in several parts: In the middle, the heat map for each day of the month is visible. By default, it shows the average speed for the current month, but it is possible to select another month and another indicator at the top. For each day, a percentage of data that has been correctly received is displayed.

There are several plots on the sides and the bottom. They show the following indicators over time: travel time, fluidity index, congestion length, average speed, total travel time and total travel distance. If they select time frame is a day, each figure will feature a blue plot line and a horizontal red line for the average value. If the selected value is a week or a month, total travel time and total travel distance will turn into histograms to show the total value for each day. The

Data quality module

The data quality module is divided into 3 sub-modules: current sensor status, data quality statistics and data quality statistics per lane.

The current sensor status module, as shown in figure 6, shows a map of the city with each sector marked with pins, colored based on the data quality. By zooming in, it is possible to see the different sensors (circle), repeaters (triangle) and access points (rectangle) installed.

Between each sector, a percentage shows the counting errors. This correspond to the difference of counted vehicles between the sectors: ideally it should stay in the same order of magnitude. A large difference can be indicative of low data quality in some of the sensors of those sectors. On the right panel, a table for the data and current status of each sensor can be seen, with the current vehicle count and average speed measured for the current time frame (in the last hour by default). It is possible to click on the name of the elements in the table to focus on them in the map. The time period of the displayed data can be selected at the top of the interface.

The data quality statistics module, shown in figure 7, is divided into 3 parts. On the bottom is heat map of the number of counting errors for the selected day, for each sector at each hour. On the right is an area chart of the data status, divided in 3 categories: correctly received, partially received and not received. It shows the proportion of data from sensors that has been received or not. Finally, on the left is a histogram of the percentage of sensors in operation. That is to say the number of sensors that sent either full data or partial data.

Conclusion and perspectives

In this article we described the Grenoble Traffic Lab Rocade (GTL-Rocade), an experimental platform for advanced traffic research. The objective of this platform is to use real-time traffic information using sensors to calculate and provide macroscopic indicators. Futhermore, we can use this data to compute traffic predictions.

The data collected by this platform has been subject to several internships and been used for research works. GTL-Rocade serves as the basis for GTL-Ville, a more ambitious project that extended our network of sensors to the major urban arterials of Grenoble in order to have wider city-level coverage of traffic behaviour and combines it with traffic data coming from heterogeneous sensors (e.g., magnetometers and GPS-equipped vehicles).

7.

Figure 1 :

 1 Figure 1: Three-level architecture of GTL. Level 1: physical layer, Level 2: data processing and applications, Level 3: results display.

  On the right panel, a map is used to represent the whole south-ring. The blue pins show the onramps, the purple ones the off-ramps. When you select a pin, its name is displayed in the panel From / To on the left side. A path is defined by an on-ramp and an off-ramp. You can select a blue pin as an origin and a red pin as a destination to trace a particular path. You can change at any moment. There are 2 main panels in the left side. The first panel in the upper part displays the origin/destination names and the time information about the prediction. The second panel

Figure 4 :Figure 3 :

 43 Figure 4: Interface for the prediction module

Figure 5 :

 5 Figure 5: Interface for the statistics module

Figure 6 :

 6 Figure 6: Interface for the current sensor status submodule of the data quality module

Figure 7 :

 7 Figure 7: Interface for the data quality statistics submodule of the data quality module

3. Methods and models 3.1 Indicators

	Pre-processed data is used to compute, for present data and predictions, the following traffic
	indicators :
	 the travel time [min]
	 the number of vehicles
	 the congestion length [km]
	 the fuel consumption [L/100km]
	 the CO2 emissions [kg/100km] and NOx emissions [g/100km] for an average family car
	 the safety index (s)

Acknowledgements

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement 694209). We thank the help and participation of V. Bertrand, R. Piotaix, I. Bellicot, P. Bellemain, A.

Andreev, A. Ladino-Lopez, L. León-Ojeda, E. Lovisari, F. Morbidi, H. Fourati, F. Garin, A. Kibangou.

8.


Éric Fusy

New bijective links on planar maps via orientations

Keywords: 2000 Mathematics Subject Classification. Primary 05A15; Secondary 05C30 bijections, planar maps, bipolar orientations. 1

New bijective links on planar maps via orientations

Introduction

Planar maps (connected graphs equipped with a planar embedding) are a rich source of structural correspondences and enumerative results. For counting purpose, all planar maps (shortly called maps) are here assumed to be rooted, that is, they have a marked oriented edge with the outer face on its left. As discovered by Tutte in the 60's [START_REF] Tutte | A census of planar maps[END_REF], many families of maps (eulerian, triangulations, quadrangulations...) have strikingly simple counting sequences, which are reminiscent of formulas for families of plane trees. Tutte's method is based on generating functions. At first a recursive decomposition of maps by root edge deletion is translated to a recurrence on the counting sequence, and then to a functional equation satisfied by the associated generating function. Solving this equation yields a formula for the counting sequence (by coefficient extraction). Tutte's method has the advantage of being quite automatic, but requires an involved machinery -the quadratic method-to solve equations on generating functions [START_REF] Tutte | The enumerative theory of planar maps[END_REF].

By now there is a bijective approach, introduced by Schaeffer in his thesis [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF], to prove counting formulas for many map families. The main ingredients are as follows: given a family of map M, one searches a regular combinatorial structure -typically an orientation with simple outdegree conditions-specific to the maps in M, which gives a way to associate with each map of M a tree with simple degree conditions. Conversely the map is recovered by performing local operations on the tree so as to close the faces one by one. The bijection ensures that the counting sequence of M is equal to the counting sequence of the associated tree family, which has typically a closed formula involving binomial coefficients.

These enumerative techniques (Tutte's recursive method or Schaeffer's bijective approach) yield thus an extensive table of counting formulas for families of maps. By examining such a table, one notices that seemingly unrelated map families are equinumerous. This asks for bijective explanations as direct as possible to understand the underlying structural correspondences. On a few instances there already exist very simple bijective constructions. Such bijections are of a type different from the above mentioned bijective constructions from trees. Indeed, they are from map to map and operate directly on the embedding in a simple local way. Let us mention the classical duality construction between maps with i vertices and j faces and maps with j vertices and i faces, the radial mapping between maps with n edges and 4-regular maps with n vertices, and the so-called trinity mapping between bipartite 3-regular maps with 2n vertices and eulerian maps with n edges (the two latter constructions can be traced back to Tutte [START_REF] Tutte | A census of planar maps[END_REF]). We have observed two further coincidences: (i): non-separable maps with n edges are equinumerous to so-called irreducible triangulations (triangulations of the 4-gon with no separating triangle) with n + 3 vertices, (ii): loopless maps with n edges are equinumerous to triangulations with n + 3 vertices. In this article, we describe new bijective constructions for proving (i) and (ii). To wit, the bijection for (i) can be seen as a direct map-to-map correspondence. But it borrows ideas from the above mentioned bijective constructions of maps from trees. At first we associate a combinatorial structure with each of the two map-families: plane bipolar orientations for non-separable maps and transversal structures for irreducible triangulations (these are defined in Section 2). We show in Section 3 that these structures are closely related: to each plane bipolar orientation O is associated in a bijective way a so-called N -avoiding plane bipolar poset P = φ(O), which yields in turn a transversal structure X = φ ′ (P ); the mapping Φ = φ ′ • φ is bijective onto so-called N -avoiding transversal structures.

Then, the correspondence Φ specialises to a bijection, described in Section 4, between non-separable maps and irreducible triangulations. The bijection, denoted by F 1 , is based on the two following properties:

• each non-separable map has a minimal plane bipolar orientation and each irreducible triangulation has a minimal transversal structure; • the correspondence Φ matches the plane bipolar orientations that are minimal on their nonseparable maps with the transversal structures that are minimal on their irreducible triangulations. As described in Section 5, the bijection F 1 yields in turn a bijection, denoted F 2 , for proving (ii). We make use of two classical decompositions: a loopless map is decomposed into a non-separable map, called the core, and a collection of components that are smaller loopless maps; whereas a triangulation is decomposed into an irreducible triangulation, called the core, and a collection of components that are smaller triangulations. The key observation is that the two decompositions are parallel, for a convenient choice of the size parameters. The bijection F 2 is thus specified recursively: the cores are matched by the bijection F 1 , and the components are matched recursively by F 2 . Let us mention that another bijective proof of (ii) has been described by Wormald [Wor80], still recursive but based on different principles (in [START_REF] Wormald | A correspondence for rooted planar maps[END_REF], an isomorphism is established between the generating tree of loopless maps and the generating tree of triangulations with an additional catalytic variable), see the discussion after Theorem 19. To sum up, the whole bijective scheme of the article is shown in Figure 1.

Preliminaries

2.1. Planar maps. A planar map, shortly called a map, is a connected unlabelled planar graph embedded in the plane with no edge-crossings, the embedding being considered up to continuous deformation. Loops and multiple edges are allowed. In addition to the vertices and edges of the graph embedded, a map has faces, which are the maximal connected areas of the plane split by the embedding. The unbounded face is called the outer face, the other ones are called inner faces. Edges and vertices are said to be inner or outer whether they are incident to the outer face or not. A corner of a map is a triple (e, v, e ′ ) where v is a vertex and e and e ′ are two consecutive edges in clockwise order around v.

A map is rooted by distinguishing and orienting an edge, called the root, with the condition that the root has the outer face on its right (equivalently, it is a map with a distinguished corner incident to the outer face). The origin of the root is called the root vertex. In this article we will consider the following families of (rooted) planar maps:

• Loopless maps. A loopless is a map such that each edge has two distinct extremities. Multiple edges are allowed. • non-separable maps. A map is non-separable if it is loopless and the deletion of any one vertex does not disconnect the map. Multiple edges are allowed. • Triangulations. A triangulation is a map with no loop nor multiple edges and with all faces of degree 3. These correspond to maximal planar graphs embedded in the plane. • Irreducible triangulations. A triangulation of the 4-gon is a map with no loop nor multiple edges, with a quadrangular outer face and triangular inner faces. An irreducible triangulation of the 4-gon, shortly called irreducible triangulation, is a triangulation of the 4-gon such that the interior of any 3-cycle is a face.

Plane bipolar orientations.

A bipolar orientation on a connected graph G is an acyclic orientation with a unique source (vertex with only outgoing edges) denoted by s and a unique sink (vertex with only ingoing edges) denoted by t. Equivalently, the partial order induced on the vertices by the orientation has a unique minimum and a unique maximum. Bipolar orientations constitute the natural combinatorial structure characterising 2-connectivity. Indeed, as is well known [START_REF] De Fraysseix | Bipolar orientations revisited[END_REF], a graph G with two marked vertices s and t admits a bipolar orientation with source s and sink t if and only if G is non-separable upon connecting s and t by an edge.

The source and the sink of the bipolar orientation are also called the poles or the special vertices. The other vertices are said to be non-special. A plane bipolar orientation is a bipolar orientation on a planar map M such that the source and the sink are outer vertices of M . It is convenient when considering plane bipolar orientations to draw two half-lines starting respectively from s and t and reaching into the outer face. The outer face is thus split into two unbounded faces, which are called the special faces; looking from s to t, the one on the left is called the left special face and the one on the right is called the right special face. As described in [START_REF] De Fraysseix | Bipolar orientations revisited[END_REF][START_REF] Felsner | Bijections for Baxter families and Related Objects[END_REF], plane bipolar orientations have the nice property that they are characterised by two simple local properties, one around vertices and one around faces, see Figure 2(a): (V): Around each non-special vertex, the edges form a nonempty interval of outgoing edges and a nonempty interval of ingoing edges. (F): The contour of each inner face f is made of two oriented paths with same origin s f and same end t f . The two special faces are each bordered by a path that goes from s to t.

Given Property (V), we define the left lateral face of a non-special vertex v as the face in the corner between the last ingoing edge and the first outgoing edge in clockwise order around v; define similarly the right lateral face of v as the face in the corner between the last outgoing edge and the first ingoing edge in clockwise order around v. Given an inner face f , the vertices s f and t f are respectively called the source and the sink of f . The path from s f to t f that has the exterior of f on its left is called the left lateral path of f and is denoted P ℓ (f ); the path from s f to t f that has the exterior of f on its right is called the right lateral path É. Fusy of f and is denoted P r (f ). The last edge of P ℓ (f ) is called the topleft edge of f and the first edge of P r (f ) is called the bottomright edge of f . The vertices of P ℓ (f )\{s f , t f } are called left lateral vertices of f , and the vertices of P r (f )\{s f , t f } are called right lateral vertices of f . The paths bordering the left special face and the right special face are called respectively the left outer path and the right outer path.

It is well known that a plane bipolar orientation O induces a partial order on the edge-set: e ≤ e ′ if and only if there exists an oriented path passing by e before passing by e ′ . In other words ≤ is the transitive closure of the binary relation: e ≺ e ′ if and only if there is a vertex v such that e is ingoing at v and e ′ is outgoing at v.

Due to a classical duality relation satisfied by plane bipolar orientations [START_REF] De Fraysseix | Bipolar orientations revisited[END_REF], there is a partial order on the face-set and another partial order, called dual, on the edge-set. Precisely, given two faces f and f ′ (special or not), write f ≺ F f ′ if there is an edge of O with f on its left and f ′ on its right; the transitive closure of ≺ F is a partial order, called the left-to-right order on the faces of O. And the dual order on the edge-set, denoted ≤ * , is defined as the transitive closure of the relation: e ≺ * e ′ (with e and e ′ edges of O) if and only if there exists a face f of O such that e is in the left lateral path and e ′ is in the right lateral path of f . Given a plane bipolar orientation with no multiple edges, a transitive edge is an edge whose two extremities are connected by an oriented path of length at least 2. A plane bipolar poset is a plane bipolar orientation with at least 3 vertices, with no multiple edges, and with no transitive edges. The terminology refers to the fact that a plane bipolar poset is a planarly embedded Hasse diagram representing a poset.

The following property is easily checked from Condition (F):

Fact 1. A plane bipolar orientation with at least 3 vertices is a plane bipolar poset if and only if the two lateral paths of each inner face have length at least 2.

An important remark to be used later is that each inner face f of a plane bipolar poset has at least one lateral vertex on each side: the last vertex of P ℓ (f )\{s f , t f } is called the topleft lateral vertex of f and the first vertex of P r (f )\{s f , t f } is called the bottomright lateral vertex of f . Given a plane bipolar poset, a N -pattern is a triple (e 1 , e 2 , e 3 ) of edges such that e 1 and e 2 have the same origin v, e 2 and e 3 have the same end v ′ , e 1 follows e 2 in clockwise order around v, and e 3 follows e 2 in clockwise order around v ′ . The edge e 2 is called the central edge of the N -pattern. A N-pattern is defined similarly, upon replacing clockwise by counterclockwise. Plane bipolar posets with no N -pattern are said to be N -avoiding; these play an important role in the bijections to be given next.

Transversal structures.

Transversal structures play a similar part for irreducible triangulations as plane bipolar orientations for non-separable maps.

Let us give the precise definition. Given a rooted irreducible triangulation T , denote by N , E, S, W the outer vertices of T in clockwise order around the outer face, starting from the origin of the root. A transversal structure of T is an orientation and a bicoloration of the inner edges of T , say each inner edge is red or blue, such that the following conditions are satisfied, see Figure 2(b) 1 .

(T1): The edges incident to an inner vertex of T form in clockwise order: a nonempty interval of outgoing red edges, a nonempty interval of outgoing blue edges, a nonempty interval of ingoing red edges, and a nonempty interval of ingoing blue edges. (T2): The edges incident to N , E, S, and W are respectively ingoing red, ingoing blue, outgoing red, and outgoing blue. Transversal structures were introduced by He [START_REF] He | On finding the rectangular duals of planar triangulated graphs[END_REF] under the name of regular edge-labellings. They were further investigated by the author [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF] and have many applications in graph drawing: straight-line drawing [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF], visibility drawing [START_REF] Kant | Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems[END_REF], rectangular layouts [START_REF] Kant | Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems[END_REF]. Transversal structures characterise triangulations of the 4-gon that are irreducible. Indeed, irreducibility is necessary, and each irreducible triangulation admits a transversal structure [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF]. Moreover, transversal structures are closely related to plane bipolar orientations by the following property: Fact 2. Let X be a transversal structure on an irreducible triangulation T having at least one inner vertex. Then the oriented map X r formed by the red edges and the vertices of T \{W, E} is a plane bipolar poset, called the red bipolar poset of X. Similarly, the oriented map X b formed by the blue edges and the vertices of T \{S, N } is a plane bipolar poset, called the blue bipolar poset of X. Proof. The fact that X r and X b are plane bipolar orientations was proved in [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF] (the main argument is that a monocoloured circuit of X would have a monocolored chordal path of the other color inside, which is not possible by Condition T1). Clearly in each inner face f of X r , the two lateral paths are not both of length 1, as T has no multiple edge. Hence, f has at least one lateral vertex v on one side (left or right), so f has at least one blue edge inside by Condition (T1). But, by condition (T1) again, such a blue edge goes from a left lateral vertex of f to a right lateral vertex of f . Hence both lateral paths of f have length greater than 1, so X r is a plane bipolar poset by Fact 1.

A transversal structure is called N -avoiding if both its red and its blue bipolar posets are N -avoiding.

Bijections between plane bipolar orientations and N -avoiding structures

This section covers the top-line of the diagram shown in Figure 1. We present a bijective mapping Φ from plane bipolar orientations to N -avoiding transversal structures; Φ is the composition of two bijections φ and φ ′ : φ maps a plane bipolar orientation to an N -avoiding plane bipolar poset, and φ ′ completes an N -avoiding plane bipolar poset into an N -avoiding transversal structure.

3.1. From plane bipolar orientations to N -avoiding plane bipolar posets. Let O be a plane bipolar orientation. We associate with O an oriented planar map P = φ(O) as follows, see Figure 3(a)-(c).

• Add two outer edges. Add two edges ℓ and r going from the source to the sink of O, so that the whole map is contained in the 2-cycle delimited on the left by ℓ and on the right by r. The augmented bipolar orientation is denoted O. • Insert the vertices of P . A vertex of P , depicted in white, is inserted in the middle of each edge of O. The vertex inserted in the edge ℓ is denoted s P , and the vertex inserted in the edge r is denoted t P . • Insert the edges of P . Edges of P are planarly inserted in the interior of each inner face f of O so as to create the following adjacencies, see Figure 4(a): the vertices of P in the left lateral path of f are connected to the vertex of P in the bottomright edge of f ; and the vertices of P in the right lateral path of f are connected to the vertex of P in the topleft edge of f . The inserted edges are directed from the left lateral path to the right lateral path of f . Lemma 3. Let O be a plane bipolar orientation with n edges. Then the oriented planar map P = φ(O) is an N -avoiding plane bipolar poset with n + 2 vertices. The source of P is the vertex s P and the sink of P is the vertex t P .

When P and the augmented bipolar orientation O are superimposed, there is exactly one non-special vertex v of O in each inner face f of P : the outgoing edges of v are incident to the left lateral vertices of f and the ingoing edges of v are incident to the right lateral vertices of f , see Figure 4(b).

Proof. Let us first prove that P is acyclic. Given two vertices v and v ′ of P , write v ≺ P v ′ if there is an edge of P from v to v ′ . Let e and e ′ be the edges of O that respectively correspond to v and v ′ . Note that v ≺ P v ′ implies e ≺ * e ′ . Hence the transitive closure of ≺ P corresponds to a suborder of ≤ * , so P is acyclic. To prove bipolarity, observe that, for each vertex v of P distinct from s P and t P , the corresponding edge e of O has one inner face of O on each side. Hence, by definition of φ, v has at least one ingoing edge in the face on the left of e (possibly more than one if e is the bottomright edge of that face) and at least one outgoing edge in the face of O on the right of e (possibly more than one if e is the topleft edge of that face).

Next, the rules for inserting the edges of P easily imply that each non-special vertex v of O gives rise to an inner face f v of P such that the edges of P outgoing at v are incident to the left lateral vertices of f v and the edges of P ingoing at v are incident to the right lateral vertices of f v , see Figure 4(b). In addition the left lateral path of f v has length Outdeg(v) + 1 and the right lateral path of f v has length Indeg(v) + 1. Hence every inner face of P of the form f v has its two lateral paths of length greater than 1. Claim. The number of non-special vertices of O is equal to the number of inner faces of P . Proof of the claim. Write V (M ), E(M ) and F (M ) for the sets of vertices, edges, and inner faces of a map M and write deg(f ) for the number of edges on the contour of an inner face f . By definition of φ, The claim ensures that every inner face of P is of the form f v for some non-special vertex v of O. Hence every inner face of P has its two lateral paths of lengths greater than 1, so P is a plane bipolar poset by Fact 1.

|V (P )| = |E( O)| and E(P ) = f ∈F ( e O) (deg(f ) -1) = 2|E( O)| -2 -|F ( O)|.
Finally, the fact that P has no N -pattern is due to the two following observations: i) two edges of P with same origin are inside the same face of O, and two edges of P with same end are inside the same face of O, hence any N -pattern must be inside a face of O; ii) there is no N -pattern of P inside a face of O.

As we prove next, the mapping φ is in fact a bijection and has an explicit simple inverse. Given a bipolar poset P (N -avoiding or not), let O = ψ(P ) be the oriented planar map defined as follows:

• Next we prove that ψ is also the right inverse of φ when restricted to N -avoiding structures.

Lemma 5. For any plane bipolar poset P , the oriented map O = ψ(P ) is a plane bipolar orientation. In addition φ(O) = P if P is N -avoiding.

Proof. Let v, v ′ be two vertices of O, and let f, f ′ be the faces of P corresponding respectively to v and v ′ . Clearly, if there is an oriented path of edges of O going from v to v ′ , then f is smaller than f ′ for the left-to-right order on the faces of P . Hence, O is acyclic. In addition, each vertex v = {s, t} of O has indegree equal to the number of left lateral vertices and outdegree equal to the number of right lateral vertices of the corresponding inner face of P . Hence, s is the only source and t the only sink of O, so O is bipolar. Now assume that P is N -avoiding, and let us now show that φ(O) = P . Recall that the first step of φ is to add two edges from s to t, yielding an augmented map O. Consider the oriented map M obtained by superimposing O and P , that is, there is a vertex of P in the middle of each edge of O and a vertex of O inside each face of P , see Figure 3(b). Call P -vertices and P -edges the vertices and edges of M that come from P , and call O-vertices and O-edges the vertices and edges of M that come from O. Note that a P -edge corresponds to an edge of P , but an O-edge corresponds to a half-edge of O.

Let v be a P -vertex. By definition of ψ (and by Property (V) of plane bipolar orientations), the edges of M incident to v form in clockwise order: a nonempty interval of outgoing P -edges, one ingoing O-edge, a nonempty interval of ingoing P -edges, and one outgoing O-edge. Hence any P -edge inside an inner face f of O must go from a P -vertex in the left lateral path of f to a P -vertex in the right lateral path of f . Thus the P -edges inside f are naturally ordered from down to top; in this order, two consecutive edges are said to be meeting if they share a vertex and parallel otherwise. By a simple counting argument, the number of P -edges inside f is deg(f ) -1p(f ), where p(f ) is the number of parallel consecutive P -edges inside f and def(f ) is the degree of f . As in the proof of Lemma 3, write V (M ), E(M ), and F (M ) for the sets of vertices, edges, and inner faces of a map M . From the above discussion, the total number of P -edges satisfies (1) From Lemma 4 and Lemma 5 we obtain our first bijection: Proposition 6. For n ≥ 1 and i ≥ 0, the mapping φ is a bijection between plane bipolar orientations with n edges and i non-special vertices, and N -avoiding plane bipolar posets with n non-special vertices and i inner faces. The inverse mapping of φ is ψ.

|E(P )| = f ∈F ( e O) deg(f ) -1 -p(f ) = 2|E( O)| -2 -|F ( O)| - f ∈F ( e O) p (
Remark. As recalled in Section 2.2, any bipolar orientation O on a graph G = (V, E) (planar or not) gives rise to a partial order P = β(O) on E, called edge-poset, according to the precedence order of the edges along oriented paths (observe that no embedding is needed to define this poset). It is well known that the mapping β is indeed a bijection between bipolar orientations on graphs and so called N -free posets, which are posets with no induced N in the Hasse diagram [START_REF] Habib | On some complexity properties of N-free posets with bounded decomposition diameter[END_REF], that is, no quadruple (v 1 , v 2 , v 3 , v 4 ) of vertices such that the only adjacencies on these vertices are: an edge from v 1 to v 3 , an edge from v 2 to v 4 and an edge from v 1 to v 4 . Moreover, it is possible to enrich this construction so as to take a planar embedding into account: the planar embedding of the plane bipolar orientation turns to a so-called 2-realizer of the associated poset [START_REF] De Fraysseix | Planarity and edge poset dimension[END_REF].

Our mapping φ shares some resemblance with this classical construction, but there are significant differences. First, the bipolar poset obtained from φ might have induced N in the form of N-patterns (due to the embedding, an induced N can appear either as an N -pattern or as an N-pattern). Second, our bijection has the nice feature that it operates directly on the embedding, in both directions (φ and ψ). The mapping φ is actually just a simple adaptation of β so as to take the embedding into account. In contrast, φ -1 = ψ is not just an adaptation of β -1 . Indeed ψ is significantly simpler, it operates on the embedding in a local way, whereas β -1 requires some non-local manipulations on the edge-poset.

3.2.

From N -avoiding plane bipolar posets to N -avoiding transversal structures. The next step is to complete an N -avoiding plane bipolar poset into a transversal structure. The procedure, called φ ′ , is very similar to φ. Precisely, given a plane bipolar poset P (N -avoiding or not) the associated transversal structure X = φ ′ (P ) is defined as follows, see Figure 3(c)-(d): • Create the outer quadrangle. Insert one vertex, denoted W , in the left special face of P and one vertex, denoted E, in the right special face of P . Connect W and E to the source and sink of P , denoted respectively by S and N , thus creating an outer quadrangle with vertices (W, N, E, S) in clockwise order. The bipolar poset augmented from P by insertion of the quadrangle -edges of the quadrangle oriented from S toward N -is denoted P . • Insert the blue edges. For each inner face f of P , insert (in a planar way) blue edges inside f so as to create the following adjacencies, see Figure 4(c): left lateral vertices of f are connected to the bottomright lateral vertex of f , and right lateral vertices of f are connected to the topleft lateral vertex of f . The inserted blue edges inside f are directed from the left lateral vertices to the right lateral vertices of f . In other words, f is triangulated by transversal blue edges in the unique way avoiding blue N -patterns inside f .

Lemma 7. Let P be a plane bipolar poset. Then φ ′ (P ) is a transversal structure whose red bipolar poset is P and whose blue bipolar poset is N -avoiding.

Proof. Clearly X := φ ′ (P ) is a transversal structure (conditions (T1) and (T2) are satisfied) whose red bipolar poset is P . The blue bipolar poset is N -avoiding due to the two following observations: i) two blue edges with the same origin are inside the same face of P , and two blue edges with the same end are inside the same face of P , hence any blue N -pattern must be inside a face of P ; ii) there is no blue N -pattern inside a face of P .

Call ψ ′ the mapping that associates to a transversal structure its red bipolar poset.

Proposition 8. For n ≥ 1 and i ≥ 0, the mapping φ ′ is a bijection between N -avoiding plane bipolar posets with n non-special vertices and i inner faces, and N -avoiding transversal structures with n inner vertices and n + i + 1 red edges. The inverse mapping of φ ′ is ψ ′ .

Proof. According to Lemma 7, ψ ′ (φ ′ (P )) = P for any plane bipolar poset P , so ψ ′ is the left inverse of φ ′ . Let us show that ψ ′ is also the right inverse of φ ′ when the mappings are restricted to N -avoiding structures. Let X be an N -avoiding transversal structure, with X r := ψ ′ (X) its red bipolar poset and X b its blue bipolar poset. When applying φ ′ to X r , each inner face f of X r is triangulated by transversal blue edges going from a left lateral vertex to a right lateral vertex of f . It is easily checked that the only such N -avoiding configuration is the one where all edges are incident either to the topleft or to the bottomright lateral vertex of f . In other words, the blue edges inside f are placed according to the insertion process of φ ′ , hence φ ′ (P ) = X. Finally, the parameter-correspondence is due to the Euler relation, which ensures that a plane bipolar poset with n non-special vertices and i inner faces has n + i + 1 edges.

To conclude, we have described a bijection Φ = φ ′ •φ between plane bipolar orientations with n ≥ 1 edges and i + 2 vertices and N -avoiding transversal structures with n inner vertices and n + i + 1 red edges. The bijection Φ operates in two steps φ and φ ′ , the intermediate combinatorial structures being the N -avoiding plane bipolar posets.

Counting Baxter families.

Plane bipolar orientations with n edges and i non-special vertices are known to be counted by the coefficients

(2) Θ n,i := 2 n(n + 1) 2 n + 1 i n + 1 i + 1 n + 1 i + 2 .
The formula has first been proved by Rodney Baxter [START_REF] Baxter | Dichromatic polynomials and Potts models summed over rooted maps[END_REF], guessing the answer from a recurrence satisfied by the counting sequence; a direct computation based on the "obstinate Kernel method" is due to Bousquet-Mélou [START_REF] Bousquet-Mélou | Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels[END_REF]. A bijective proof has been found recently [START_REF] Fusy | Bijective counting of plane bipolar orientations and Schnyder woods[END_REF]. Summing over i the coefficients Θ n,i , the number of plane bipolar orientations with n edges is

θ n := i 2 n(n + 1) 2 n + 1 i n + 1 i + 1 n + 1 i + 2 .
The numbers θ n , called the Baxter numbers (after another Baxter, Glen Baxter, whose name is given to a family of permutations counted by θ n ), surface recurrently in the enumeration of combinatorial structures, see [START_REF] Felsner | Bijections for Baxter families and Related Objects[END_REF] for a recent survey on "Baxter families". Our bijections with N -avoiding structures, as described in Section 3, bring new Baxter families to the surface:

Proposition 9. For n ≥ 1 and i ≥ 0, the number Θ n,i counts:

• N -avoiding plane bipolar posets with n non-special vertices and i inner faces,

• N -avoiding transversal structures with n inner vertices and n + i + 1 red edges.

Taking into account the parameter n only, these structures are counted by the Baxter number θ n .

4. Bijection between non-separable maps and irreducible triangulations 4.1. Non-separable maps as specific plane bipolar orientations. For rooted maps, plane bipolar orientations are always assumed to have the root edge going from the source to the sink. As already mentioned in Section 2.2, bipolar orientations are naturally associated with the property of non-separability; a rooted map is non-separable if and only if it admits a plane bipolar orientation. Even more is true, namely, each rooted non-separable map can be endowed with a specific plane bipolar orientation in a canonical way. Given a plane bipolar orientation, we define a left-oriented piece, shortly a LOP, as a 4-tuple (v 1 , v 2 , f 1 , f 2 ) made of two distinct vertices v 1 , v 2 and two distinct faces f 1 , f 2 of O such that the following conditions are satisfied, see Figure 5(a): • the vertex v 1 is the sink of f 2 and is a left lateral vertex of f 1 ,

• the vertex v 2 is a right lateral vertex of f 2 and is the source of f 1 .

Note that v 1 and v 2 must be non-special vertices and f 1 and f 2 must be inner faces.

Fact 10 ([dFOdMR95, OdM94]). A rooted map is non-separable if and only if it admits a bipolar orientations. A rooted non-separable map M has a unique plane bipolar orientation with no LOP, called the minimal plane bipolar orientation of M .

The terminology is due to the fact that the set of plane bipolar orientations of a fixed rooted nonseparable map is a distributive lattice, the minimal element of the lattice being the bipolar orientation with no LOP, see [START_REF] Ossona De Mendez | Orientations bipolaires[END_REF]. The set of plane bipolar orientations with no LOP is denoted O min .

Lemma 11 (link with plane bipolar posets). Let O be a plane bipolar orientation, and let P = φ(O) be the associated N -avoiding plane bipolar poset. Then O has no LOP if and only if P has no LOP.

Proof. Assume that O has a LOP (v 1 , v 2 , f 1 , f 2 ). Let w 1 be the vertex of P inserted in the bottomright edge of f 2 and w 2 the vertex of P in the topleft edge of f 1 . Let f ′ 1 be the face of P corresponding to v 2 and f ′ 2 the face of P corresponding to v 1 . Then (w 1 , w 2 , f ′ 1 , f ′ 2 ) is easily checked to be a LOP of P , as shown in Figure 5(b).

Conversely, assume that P has a LOP (w 1 , w 2 , f ′ 1 = f v1 , f ′ 2 = f v2 ), with v 1 and v 2 the vertices of O associated respectively to the two faces f ′ 2 and f ′ 1 of P . Let f 1 be the face of O containing the ingoing edges of w 1 , and let f 2 be the face of O containing the outgoing edges of w 2 . Let us first check that f 1 and f 2 can not be equal. Assume f 1 = f 2 = f , then w 1 is in the right lateral path and w 2 is in the left lateral path of f ; since P = φ(O) and since there is a path from w 2 to w 1 (due to the LOP of P ), the vertices w 2 and w 1 must be adjacent, so the LOP of P is in fact reduced to an N -pattern, a contradiction. Thus f 1 and f 2 are distinct. From the definition of ψ and the fact that w 2 and w 1 are not adjacent, it is easily checked that 5(b).

(v 1 , v 2 , f 1 , f 2 ) is a LOP of O = ψ(P ), see Figure
Let P min be the set of plane bipolar posets with no LOP. Note that an N -pattern-with e its central edge-in a plane bipolar poset induces a LOP (v 1 , v 2 , f 1 , f 2 ) where v 1 is the end of e, v 2 is the origin of e, f 1 is the face on the right of e, and f 2 is the face on the left of e. Hence P min is also the set of N -avoiding plane bipolar posets with no LOP, which by Lemma 11 is in bijection with O min . Thus we obtain (3)

O min ≃ φ P min .

Irreducible triangulations as specific transversal structures.

As we recall here from [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF], one can endow an irreducible triangulation with a specific transversal structure in a canonical way. Given a transversal structure X, an alternating 4-cycle of X is a cycle of four edges that alternate in color, that is, the cycle has two opposite red edges and two opposite blue edges. Given v a vertex of R, let e and e ′ be the two edges of R incident to v, such that e ′ follows e in a counterclockwise walk around R; e is called the left-edge of v and e is called the right-edge of v. A boundary incidence of R is the incidence of an edge e inside R with a vertex v on R; it is called a left incidence if e has the color of the left-edge of v and a right incidence if e has the color of the right-edge of v. As proved in [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF], R is of two possible types: either all boundary incidences for R incidences are left incidences, in which case R is called a left alternating 4-cycle, or all boundary incidences of R are right incidences, in which case R is called a right alternating 4-cycle.

v 1 v 2 f 1 f 2 v 1 v 2 f 1 f 2 f ′ 1 f ′ 2 w 1 w 2 w 1 s R t R w 2 w 1 s R t R w 2 (a) (b) (c) f ′ 2 f ′ 1 Figure 5.
Let us give a slightly different formulation. By Condition (T1), the cycle R is made of two oriented paths of length 2 with the same origin s R and the same end t R , which are called the source and the sink of R. Let X R be X restricted to R and its interior, forgetting the colors and directions of the edges of R. Then, if R has at least one interior vertex, X R is a transversal structure. If s R is source of red edges, R is a left alternating 4-cycle; if R is source of blue edges, R is a right alternating 4-cycle. In the degenerated case where R has no vertex inside-thus it has a unique edge e inside-consider the triple formed by e and the two edges of R of the same color as e. Then either the triple forms an N-pattern, in which case R is a left alternating 4-cycle, or the triple forms an N -pattern, in which case R is a right alternating 4-cycle.

Fact 12 ([Fus09]). A triangulation of the 4-gon is irreducible if and only if it admits a transversal

structure. An irreducible triangulation admits a unique transversal structure with no right alternating 4cycle, called its minimal transversal structure.

Again the terminology refers to the fact that the set of transversal structures of an irreducible triangulation is a distributive lattice whose minimal element is the transversal structure with no right alternating 4-cycle, see [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF].

Lemma 13 (link with plane bipolar posets). Let X be an N -avoiding transversal structure, and let X r be the red bipolar poset of X. Then X has no right alternating 4-cycle if and only if X r has no LOP.

Proof. Assume that X has a right alternating 4-cycle R, the vertices of R in clockwise order being denoted (s R , w 1 , t R , w 2 ), with s R the source and t R the sink of R. Let f ′ 1 be the face of X r containing the blue edge (w 1 , t R ), and let f ′ 2 be the face of X r containing the blue edge (s R , w 2 ). As discussed at the end of the definition of right alternating 4-cycles, a right alternating 4-cycle with no vertex inside yields an N -pattern. Hence, since X is N -avoiding, R has at least one vertex inside, so the faces

f ′ 1 and f ′ 2 are distinct. It is easily checked that (w 1 , w 2 , f ′ 1 , f ′ 2 ) is a LOP, as shown in Figure 5(c). Conversely assume that X r has a LOP (w 1 , w 2 , f ′ 1 , f ′ 2 )
. Let s R be the topleft lateral vertex of f ′ 2 , and let t R be the bottomright lateral vertex of f ′ 1 . Since X is N -avoiding, X is obtained from its red bipolar poset as X = φ ′ (X r ). By definition of φ ′ (see Figure 4(c)), in X there is a blue edge from s R to w 2 and a blue edge from w 1 to t R . Hence, the 4-cycle R = (s R , w 1 , t R , w 2 ) is an alternating 4-cycle. As there are red edges inside R incident to w 1 and w 2 , s R is source of blue edges, so R is a right alternating 4-cycle.

Let T min be the set of transversal structures with no right alternating 4-cycle (minimal transversal structures). Note that an N -pattern in a transversal structure yields a right alternating 4-cycle: the cycle delimited by the faces on both sides of the central edge of the N -pattern. Hence T min is also the set of N -avoiding transversal structures with no right alternating 4-cycle, which by Lemma 13 is in bijection with P min . Thus we obtain:

(4) P min ≃ φ ′ T min .

The bijection.

To conclude, we have

O min ≃ φ P min ≃ φ ′ T min .
Hence Φ = φ ′ • φ specializes into a bijection between minimal plane bipolar orientations and minimal transversal structures. Since minimal plane bipolar orientations identify to (rooted) non-separable maps and minimal transversal structures identify to (rooted ) irreducible triangulations, we obtain a bijection, called F 1 , between these two map families. Precisely, given a rooted non-separable map M with at least 2 edges T := F 1 (M ) is obtained as follows:

• endow M with its minimal plane bipolar orientation O, the root edge being deleted,

• compute the transversal structure X associated to O: X := Φ(O),

• return T as the irreducible triangulation underlying X, rooted at the edge going from N to W , and M = F -1 1 (T ) is obtained as follows: • endow T with its minimal transversal structure, • compute the plane bipolar orientation O associated to X: O := ψ(ψ ′ (X)),

• return the rooted non-separable map M underlying O (M receives an additional root edge going from the source to the sink).

Theorem 14. For n ≥ 2, the mapping F 1 is a bijection between rooted non-separable maps with n edges and irreducible triangulations with n + 3 vertices.

Proof. The bijection results from O min ≃ T min , as discussed above. The parameter-correspondence is inherited from the parameter-correspondences of φ and φ ′ . 4.4. Counting non-separable maps. Brown and Tutte [START_REF] Brown | On the enumeration of rooted nonseparable maps[END_REF] used the recursive approach introduced by Tutte to show that the number of rooted non-separable maps with n + 1 edges and i + 2 vertices is (5) Λ n,i = (n + i)!(2ni -1)! (i + 1)!(ni)!(2i + 1)!(2n -2i -1)! .

And the number of rooted non-separable with n + 1 edges is λ n = n-1 i=0 Λ n,i , which simplifies to (6) λ n = 2(3n)! (n + 1)!(2n + 1)! .

Bijective proofs have been given later on, the first one being a correspondence with ternary trees bearing labels so as to satisfy a positivity condition [START_REF] Jacquard | A bijective census of nonseparable planar maps[END_REF]. A more direct construction has been described by Schaeffer in his PhD [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF], as a 4-to-(2n + 2) correspondence between ternary trees with n nodes and rooted non-separable maps with n + 1 edges. The correspondence is based on local "closure" operations on a ternary tree, with the effect of closing one by one the faces of the associated map.

Our bijections relating maps via specific combinatorial structures, as described in Section 4, yields the following counting results: Proposition 15. For n ≥ 1 and i ≥ 0, the number Λ n,i counts:

• rooted non-separable maps with n + 2 vertices, i + 2 faces, and whose minimal plane bipolar orientation (forgetting the root-edge) is a plane bipolar poset, • rooted irreducible triangulations with n inner vertices and whose minimal transversal structure has n + i + 1 red edges. Taking into account the parameter n only, these map families are counted by λ n .

Remark. As for rooted non-separable maps, there exists a simple 4-to-(2n + 2) correspondence between ternary trees with n nodes and rooted irreducible triangulations with n inner vertices [START_REF] Fusy | Transversal structures on triangulations: A combinatorial study and straight-line drawings[END_REF], again based on "closure" operations on the tree.

It turns out that our bijection F 1 puts in correspondence a non-separable map M and an irreducible triangulation T that have the same underlying (unrooted) ternary tree. This is no surprise, as the ternary tree associated to M (T ) is a spanning tree that arises from deleting specific edges in the minimal bipolar orientation of M (minimal transversal structure of T , resp.), whereas F 1 results from φ matching minimal plane bipolar orientations with minimal transversal structures. Hence, F 1 can be considered as a direct bijective construction on maps that has the same effect as computing the ternary tree associated to a nonseparable map and then closing the tree into an irreducible triangulation.

5. Bijection between loopless maps and triangulations 5.1. Decomposing loopless maps into non-separable components. It is well known in graph theory that a connected graph G is decomposed into a collection of non-separable components called the blocks, which are the maximal non-separable subgraphs of G [HP73, MT01]. Conversely, the process of gluing non-separable graphs at common vertices in a tree-like fashion yields any connected graph in a unique way. This classical decomposition readily adapts to rooted loopless maps [START_REF] Tutte | A census of planar maps[END_REF][START_REF] Goulden | Combinatorial Enumeration[END_REF]. For our purpose it proves convenient to define the size |M | of a rooted loopless map as its number of edges including the root. In this section we consider the vertex-map-made of a unique vertex and no edge-as a rooted loopless map. In contrast, non-separable maps are required to have at least one edge.

Fact 16. The following process:

• take a rooted non-separable map C, and order the corners of C in a canonical way as α 1 , . . . , α 2|C| ;

• take a collection M 1 , . . . , M 2|C| of rooted loopless maps; for each 1 ≤ i ≤ 2|C|, insert M i in the corner α i of C, merging the outer face of M i with the face incident to α i and the root vertex of M i with the vertex incident to α i , yields a rooted loopless map, and each rooted loopless map M is obtained in a unique way from this process.

The map C is called the core-map of M , and the (2|C|+1)-tuple D(M ) = (C; M 1 , . . . , M 2|C| ) is called the decomposition-tuple of M . (Note that the size of M is the sum of the sizes of the maps in the decompositiontuple.) 5.2. Decomposing triangulations into irreducible components. Similarly as for loopless maps, there exists a classical decomposition of triangulations into components of higher connectivity: each triangulation on the topological sphere is obtained from a collection of 4-connected triangulations (which are triangulations where all 3-cycles are facial) glued at common triangles in a tree-like fashion. The same idea -decomposition at separating 3-cycles-works as well to decompose rooted triangulations of the 4-gon into rooted irreducible components [START_REF] Tutte | A census of planar triangulations[END_REF]. First let us introduce some terminology. Given a rooted triangulation T of the 4-gon, denote by N, E, S, W the outer vertices of T in clockwise order around the outer face, with N the root-vertex; then T is called WE-diagonal if W and E are adjacent, T is called SN -diagonal if S and N are adjacent, and T is called non-diagonal otherwise. Notice that the two diagonal cases are disjoint by planarity of T . The unique rooted irreducible triangulation that is WE-diagonal is the quadrangle (N, E, S, W ) split by a diagonal (W, E); this map is called the WE-link-map. Similarly the unique rooted irreducible triangulation that is SN -diagonal is the quadrangle (N, E, S, W ) split by a diagonal (S, N ); this map is called the SN -link-map. For our purpose it is convenient to define the size of a triangulation or of a triangulation of the 4-gon T as ||T || := (|V (T )| -3). Notice that ||T || is the number of inner vertices if T is a triangulation and 2||T || is the number of inner faces if T is a triangulation of the 4-gon, by the Euler relation.

Fact 17. The following process:

• take a rooted irreducible triangulation I, and order the inner faces of I in a canonical way as f 1 , . . . , f 2||I|| ; • take a collection T 1 , . . . , T 2||I|| of rooted triangulations; for each 1 ≤ i ≤ 2||I||, substitute f i by T i in a canonical way (e.g., the outer triangle of T i fits with the contour of f i and the root vertex of T i fits with a distinguished vertex of f i ) yields a rooted triangulation of the 4-gon; and each rooted triangulation T of the 4-gon is obtained in a unique way from this process.

The map I is called the core-triangulation of T ; T is non-diagonal if I has at least one inner vertex, is WE-diagonal if I is the WE-link-map, and is SN -diagonal if I is the SN -link-map. The (2||I|| + 1)-tuple D(T ) = (I; T 1 , . . . , T 2||I|| ) is called the decomposition-tuple of T . (Note that the size of T is the sum of the sizes of the maps in the decomposition-tuple.)

As a corollary we can describe the decomposition-tuples corresponding to rooted triangulations. Indeed, in each size k ≥ 1, there is a simple bijection between rooted triangulations and rooted triangulations of the 4-gon that are not W E-diagonal. Starting from a rooted triangulation T , delete the edge following the root in counterclockwise order around the outer face; the obtained map is a triangulation of the 4-gon, and W and E are not adjacent, since the unique edge connecting them in T has been deleted. Conversely, starting from a rooted triangulation T of the 4-gon that is not W E-diagonal, add an edge between E and W . Since W and E are not adjacent in T , the obtained map T has no multiple edges (nor loops) and has clearly all faces of degree 3, so T is a triangulation.

Corollary 18. In each size k ≥ 1, rooted triangulations can be identified with rooted triangulations of the 4-gon that are not W E-diagonal, which themselves identify to decomposition-tuples whose coretriangulation is not the W E-link-map.

5.3. The bijection. Our size-preserving bijection, called F 2 , between rooted loopless maps and rooted triangulations is defined recursively from the bijection F 1 . Recall that F 1 maps a non-separable map of size at least 2 (at least one non-root edge) to an irreducible triangulation of the same size (at least one inner vertex). It is convenient here to augment the correspondence F 1 into a bijection F 1 with one object of size 1 on each side: the edge-map-made of two vertices connected by an edge-corresponds to the SN -link-map. We denote by L the family of (rooted) loopless maps including the vertex-map, by L ≤n the set of loopless maps of size at most n, and by L n the set of loopless maps of size n. Similarly, denote by T the family of (rooted) triangulations including the triangle, by T ≤n the set of triangulations of size at most n, and by T n the set of triangulations of size n. Finally, denote by N the family of (rooted) non-separable maps with at least one edge and by I the family of (rooted) irreducible triangulations with at least one inner vertex. Note that F 1 is a size-preserving bijection between N and I ∪ {SN -link-map}.

The size-preserving bijection F 2 between L and T is specified recursively as follows. First, the vertexmap-the unique rooted loopless map M such that |M | = 0-is mapped by F 2 to the triangle-map-the unique rooted triangulation T such that ||T || = 0. Given n ≥ 0, assume that F 2 is a well defined bijection from L ≤n to T ≤n , that is size-preserving: ||F 2 (M )|| = |M | for every M ∈ L ≤n .

Let us now extend the bijection F 2 to maps of size n + 1. By Fact 16, a tuple (C; M 1 , . . . , M 2|C| ) corresponds to a loopless map in L n+1 if and only if C is in N , the M i 's are in L, and |C| + i |M i | = n + 1, in which case all the M i 's must be in L ≤n . Let DL n+1 be the set of such decomposition-tuples, note that DL n+1 ≃ L n+1 . Similarly, by Fact 17 and Corollary 18, a tuple (I; T 1 , . . . , T 2||I|| ) corresponds to a triangulation in T n+1 if and only if I is in I ∪ {SN -link -map}, the T i 's are in T , and ||I|| + i ||T i || = n + 1, in which case all the T i 's must be in T ≤n . Let DT n+1 be the set of such decomposition-tuples, note that DT n+1 ≃ T n+1 . Since F 1 is a size-preserving bijection between N and I ∪ {SN -link-map} and since, by induction, F 2 is a bijection between L ≤n and T ≤n , we obtain a bijection DL n+1 ≃ DT n+1 : for (C; M 1 , . . . , M 2|C| ) ∈ DL n+1 , the associated tuple in DT n+1 is ( F 1 (C); F 2 (M 1 ), . . . , F 2 (M 2|C| )). Since DL n+1 ≃ L n+1 and DT n+1 ≃ T n+1 , we conclude that L n+1 is in bijection with T n+1 , and we call F 2 the bijection extended to L ≤n+1 .

Theorem 19. For n ≥ 0, the mapping F 2 is a bijection between rooted loopless maps with n edges and rooted triangulations with n inner vertices.

É. Fusy

Our bijection has the original feature of being a mixing of a recursive construction (the parallel recursive decompositions into non-separable/irreducible components) and a direct construction (the mapping F 2 to match non-separable/irreducible components). The advantage is that, in practice, there should be fewer levels of recursion in our bijection than in Wormald's one. Indeed, as shown in [START_REF] Banderier | Random maps, coalescing saddles, singularity analysis, and Airy phenomena[END_REF], a typical loopless map is made of a giant non-separable component -of linear size-having small connected components attached in each corner.

Let us also mention that direct bijective proofs of |T n | = a n have been found recently [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF][START_REF] Fusy | Dissections, orientations, and trees, with applications to optimal mesh encoding and to random sampling[END_REF], again based on closure operations on trees. However, no bijection with trees is known yet to explain |L n | = a n . It would be interesting to find out such a construction for loopless maps, and hopefully derive from it a direct (nonrecursive) bijection between L n and T n .

Figure 1 .

 1 Figure 1. Relations between the combinatorial structures and map families considered in the article. Bijective links are indicated by double arrows. Below each double arrow is indicated the name of the mapping for the left-to-right arrow.

Figure 2 .

 2 Figure 2. (a) Plane bipolar orientations: local conditions and an example. (b) Transversal structures: local conditions and an example.

Figure 3 .Figure 4 .

 34 Figure 3. (a) A plane bipolar orientation, (c) the associated N -avoiding plane bipolar poset, (d) the associated N -avoiding transversal structure.

  By the Euler relation, |F (P )| = |E(P )| -|V (P )| + 1, so |F (P )| = |E( O)| -|F ( O)| -1, which is equal to (|V ( O)| -2) again by the Euler relation. Hence, the number of inner faces of P is equal to the number of non-special vertices of O. △

  Insert the vertices of O. One vertex of O is inserted in each face of P . The vertex inserted in the right special face of P is denoted s and the vertex inserted in the left special face of P is denoted t. • Insert the edges of O. Each non-special vertex v of P gives rise to an edge of O that goes from the vertex of O inside the right lateral face of v to the vertex of O inside the left lateral face of v. The correspondence between non-special vertices of O and inner faces of P , as stated in Lemma 3 and shown in Figure 4(b), ensures that ψ is exactly the procedure to recover a plane bipolar orientation from its image P = φ(O). In other words: Lemma 4. For each plane bipolar orientation O, ψ(φ(O)) = O.

  f ). Moreover, |E(P )| = |V (P )| + |F (P )| -1 by the Euler relation, |V (P )| = |E( O)| by definition of φ, and |F (P )| = |V ( O)| -2 by definition of ψ. Hence |E(P )| = |E( O)| + |V ( O)| -3, which is equal to 2|E( O)| -|F ( O)| -2 again by the Euler relation. Hence, from the first expression (1) of |E(P )| obtained above, we conclude that f ∈F ( eO) p(f ) = 0, so all the p(f ) are zero, so that all consecutive P -edges in any inner face of O are meeting. As P has no N -pattern and all consecutive edges are meeting, the only possible configuration for the P -edges inside a face of O is the configuration shown in Figure4(a). In other words, the P -edges are those inserted when applying the mapping φ to O. Hence φ(O) = P .

  Figure 5. (a) A left-oriented piece (LOP) of a plane bipolar orientation. (b) Each LOP in a plane bipolar orientation O yields a LOP in P = φ(O). (c) Each right alternating 4-cycle in an N -avoiding transversal structure X yields a LOP in the red bipolar poset of X.

Remark.

  Let us make a few comments on this bijection. Denote by L n,k the family of rooted loopless maps with n edges and root-vertex of degree k, and denote by T n,k the family of rooted triangulations with n inner vertices and root-vertex of degree k + 2. The equality |L n | = |T n | is known for long [Tut62, Tut73], as both |L n | and |T n | are equal to (7) a n := 2(4n + 1)! (n + 1)!(3n + 2)! . A first bijective proof of |L n | = |T n |, more precisely of |L n,k | = |T n,k |, has been found by Wormald [Wor80], based on the observation that the generating trees (induced by root-edge-deletion) of L = ∪ n,k L n,k and ofT = ∪ n,k T n,k are isomorphic.The bijection is thus recursive; a rooted loopless map is first completely decomposed to find out the place it occupies in the generating tree of L, then the associated rooted triangulation is the one occupying the same place in the generating tree of T .

In all figures, red edges are light and blue edges are dark.

Acknowledgements. I am very grateful to Gilles Schaeffer for his encouragements to find a new bijection between loopless maps and triangulations. I thank the anonymous referee for a very detailed report that has led to a significant improvement of the presentation of the results. This work has also benefited from interesting discussions with Mireille Bousquet-Mélou, Nicolas Bonichon, and Nick Wormald.