Combinatorial structures on planar maps

Get Complete Project Material File(s) Now! »

Introduction

The aim of this chapter is first to provide a short and accessible presentation of planar maps. For a more detailed introduction, see the introductory chapter in the theses of Bernardi [8] and Schaeﬀer [99]. Then, the key point we develop is that, for several well known families of planar maps, there exists a particular combinatorial structure that characterises the maps of the family. The combinatorial structure is often an orientation with specific properties, which can be combined with a coloration of the edges such that the induced subgraph in each color has a simple form (e.g. a tree). As we will see in Chapter 3, 4, and 5, such a structure is a precious tool to study the corresponding family of maps: in each case, it makes it possible to count bijectively the family according to a size parameter and gives rise to eﬃcient algorithms for random sampling, encoding, and straight-line drawing.
After presenting planar maps in Section 1, we will focus on four examples of combinatorial structures: 1) Eulerian orientations for the family of Eulerian maps, 2) bipolar orientations for the family of 2-connected maps, 3) Schnyder woods for families related to 3-connected maps, 4) transversal structures for families related to 4-connected maps. As we will see, all these structures can be formulated in terms of orientations with prescribed outdegree for each vertex. These are called α-orientations and obey nice structural properties —in particular lattice properties— that are recalled in Section 2.
Results obtained in this chapter. Most of the results presented in this chapter are not new. The theory of α-orientations is developed in not less than 3 sources: an unpublished article by Propp [96], the thesis of Ossona de Mendez [92], and a more recent article by Felsner [48]. Our presentation of Eulerian orientations and Schnyder woods closely follows [48]. In the literature, the lattice property of bipolar orientations is studied in [92] and the correspondence with 2-orientations of quadrangulations is described in [38]; our presentation in Section 4 sketches how the lattice property of bipolar orientations is easily described via the lattice structure of 2-orientations of a quadrangulation; essentially we combine the arguments presented in [92] and in [38] so as to provide a shorter presentation of the results.
Our main contribution in this chapter is a detailed combinatorial study of transversal structures, which were introduced by Xin He —under the name of regu-lar edge-labeling— for triangulations of the 4-gon with no filled 3-cycle [73], called hereafter irreducible triangulations. We extend the definition to any planar map, show a characterisation as a transversal pair of bipolar orientations, and describe conditions of existence. Then we study the set of transversal structures of a fixed irreducible triangulation T . Our main result is Theorem 1.4 page 50, where we show that the set of transversal structures of T is a distributive lattice, with an explicit simple flip operation. Similarly as for bipolar orientations, the description is obtained via α-orientations of an associated quadrangulated map.
Motivations. The results on orientations recalled and obtained in this chapter are extensively used to develop a general bijective framework for counting planar maps, and to analyse the straight-line drawing algorithms presented in Chapter 5. Our study of transversal structures has also a specific application to a result of cartography [104], where an exhaustive generation of transversal structures is useful to obtain the best cartographic representation (the discussion is given in Section 6).

Planar maps

Definitions

Graphs. A graph G is given by a set V = {v1, . . . , vn} of vertices and a set E of unordered pairs of vertice that are called edges . An edge is classically written e = {v, v′ }. The vertices v and v′ are called the extremities of e; if v = v′ e is called a loop, otherwise e is said to connect v and v′. A multiple edge is a pair of distinct vertices connected by at least 2 edges. The degree of a vertex v is the number of edges incident to v, with multiplicity 2 for loops incident to v. A path of G is a sequence v0, e0, v1, . . . , ek, vk+1 of vertices and edges such that, for 0 ≤ i ≤ k the edge ei connects vi and vi+1. The vertices v0 and vk+1 are said to be connected by the path. The path is called simple if the vertices v0, . . . , vk+1 are diﬀerent. A graph is said to be connected iﬀ any pair of vertices are connected by a path. A cycle of G is a cyclic sequence v0, e0, v1, . . . , vk , ek such
that for each 0 ≤ i ≤ k, the edge ei connects vi to v(i+1) mod k . The cycle is simple if the vertices v0, . . . , vk are diﬀerent. A graph is oriented if all its edges are directed. An edge e from a vertex v to a vertex v′ is denoted by e = (v, v′), the vertex v is called the origin of e and v′ is called the end-vertex of e. For each vertex v, the number of edges whose origin is v is called the outdegree of v and is denoted by Outdeg(v). Similarly, the number of edges whose end-vertex is v is called the indegree of v and is denoted by Indeg(v). An oriented path is a path v0, e0, v1, . . . , ek, vk+1 such that, for 0 ≤ i ≤ k, ei goes from vi to vi+1; and a circuit is a cyclic sequence v0, e0, v1, . . . , vk , ek such that for each 0 ≤ i ≤ k, the edge ei goes from vi to v(i+1) mod k . The notion of simple oriented path and simple circuit are defined similarly as for unoriented graphs.
Embeddings. An embedding D (or drawing) of a graph G in the plane R2 is given by an injective mapping ΦV : v ∈ V → (xv , yv ) from the vertices of G to plane points, and by a mapping ΦE from the edges of G to open smooth arcs in the plane such that the extremities of any edge e are mapped by ΦV to the extremities of the arc ΦE (e). An embedding is said to be planar iﬀ the (closure of the) arcs (ΦE (e))e∈E do not meet except at common extremities, see Figure 1(a). A graph G that admits a planar embedding is called a planar graph . Notice that a planar graph G admits infinitely many planar embeddings. However it admits only finitely many if the embeddings are considered up to isotopy, i.e., two planar embeddings D0 and D1 are identified if there exists a continuous family {D(t), t ∈ [0, 1]} of planar embeddings of G such that D(0) = D0 and D(1) = D1. In the plane, this is equivalent to the existence of an orientation-preserving homeomorphism mapping D0 to D1. The isotopy relation allows us to abstract the geometry and to consider only the embeddings at the topological level.
Maps. A planar map (hereafter shortly called a map) is an isotopy class of planar embeddings of a connected planar graph. Notice that the graphs embedded are unlabelled. To state it simply, a planar map is a connected unlabelled graph drawn in the plane without edge-crossings and up to continuous deformation. Planar maps are often called plane graphs in the literature. As illustrated in Figure 1(a)-(b), a planar graph can have non-isotopic planar embeddings, so that it gives rise to several maps. Due to the topological embedding, a map has more structure than a graph. In particular, a map has faces , each face corresponding to a connected component of the plane split by the embedding. The unique unbounded face is called the outer (or infinite) face. Vertices, edges, and faces are called the 0-cells, 1-cells, and 2-cells of the map, respectively. The numbers |V |, |E|, and |F | of vertices, edges, and faces (including the outer face) of a map are related by the well known Euler’s relation: (2) |V|−|E|+|F|=2.
A pair of cells are incident to one another if one of the two cells belongs to the closed boundary of the other one, e.g. a vertex v is incident to a face f (and vice versa) if v belongs to the boundary of f . It will be convenient to see an edge e as a pair of half-edges starting at each of the two extremities of e and meeting in the middle of e, i.e., we imagine that each edge is cut at its middle into two half-edges. The face incident to a half-edge h is defined to be the face on the right of h (looking from the origin of h). The degree of a vertex v is the number of half-edges incident to v, i.e., having v as origin. If there is no loop nor multiple edges, the degree of v is its number of neighbours. The degree of a face f is the number of edges traversed during a tour of the boundary of f . Finally, let us make precise the terminology and properties concerning cycles and circuits. First, cycles and circuits will always be assumed to be simple when dealing with maps. A theorem of Jordan ensures that a cycle C partitions the plane into two regions, a bounded one called the interior of C, and an unbounded one called the exterior of C. A vertex or edge will be said to be inside C (outside of C) if it is in the interior of C (exterior of C, respectively). Concerning circuits (i.e., oriented cycles), a circuit C is said to be clockwise (shortly written cw) if the interior of C is on the right of C and is said to be counter-clockwise (shortly written ccw) otherwise .
Combinatorial encoding of maps. Even if the definition is geometric, planar maps are combinatorial objects. Indeed, a map M is encoded by the so-called half-edge structure. Given a half-edge h of M , define the opposite half-edge of h —denoted by opp(h)— as the half-edge complementing h into an edge, and define the next half-edge of h —denoted by next(h)— as the half-edge following h in counterclockwise order around the origin of h. If the half-edges of M are given distinct labels in {1, . . . , 2n }, the map M is completely encoded (up to specifying the outer face) by the two permutations σopp, which maps the label of each half-edge to the label of the opposite half-edge (hence σopp has one cycle of length 2 for each edge), and σnext, which maps the label of each half-edge to the label of the next half-edge (hence σnext has a cycle for each vertex). Notice that the permutation σface := σnext ◦ σopp maps each half-edge h to the following half-edge in clockwise order around the face incident to h. The half-edge encoding is also very convenient to handle maps as data structures; this is the data structure we have used to implement all algorithms presented in this thesis. In practice, each half-edge has a pointer to its opposite half-edge and a pointer to its next half-edge. The half-edge data structure makes it possible to navigate around a vertex, a face, to traverse a map according to various orders…
Rooted maps. Even though the encoding of maps is done via labeling of the half-edges, maps are unlabeled objects. Hence, they are subject to symmetries, which makes a combinatorial treatment more complicated. Precisely, given two maps M1 and M2, an isomorphism from M1 to M2 is a bijection φ mapping the half-edges of M1 to the half-edges of M2, preserving the opposite and next half-edge, and preserving the outer face (this last condition is dropped if maps are considered on the sphere rather than in the plane, see [8, Chap 0]). In other words, opp(φ(h)) = φ(opp(h)) and next(φ(h)) = φ(next(h)), and φ maps the half-edges of the outer face of M1 to the half-edges of the outer face of M2. An automorphism of a map M is an isomorphism from M to itself. To avoid problems due to automorphisms, it is more convenient to consider rooted maps instead of maps. A map is rooted by marking and orienting an edge so that this edge has the outer face on its left. The marked oriented edge is called the root and its origin is called the root-vertex. If no outer face is specified (map on the sphere rather then on the plane), the operation of rooting consists in marking a half-edge and choosing the face on the left as outer face, so as to get a rooted planar map. It can be proved that an automorphism Φ = Id of a map M on the sphere has no fixed half-edge, so that a rooted map has no symmetry. Notice that this property is not true for unlabeled planar graphs, i.e., a planar graph with a marked oriented edge can have nontrivial automorphisms.
Straight-line drawing. Like planar graphs, a planar map can be represented by infinitely many planar embeddings. We will focus in Chapter 5 on a very natural representation of a planar map, called straight-line drawing. A planar embedding of a map M is called a straight-line drawing if the vertices are mapped to points of a regular integer grid [0..W ] × [0..H ] and edges are mapped to segments, see Figure 1(c). The integers W and H are called the width and the height of the grid. It is well known that a planar map M with no loop nor multiple edge admits a straight-line drawing. Indeed, M can be triangulated by adding edges, and there exist straight-line drawing algorithms for triangulations, as we will see in Chapter 5.
1.2. Families of planar maps. Several families of planar maps will be con-sidered in this thesis. Our aim is to have a good understanding of the combinatorial properties of these families, in order to develop an eﬃcient algorithmics. Classical families of maps are obtained by imposing a regularity on the degrees of vertices or faces, or by imposing a higher connectivity. Much attention will be devoted to triangulated maps (all inner faces are triangles) and quadrangulated maps (all inner faces are quadrangles). These families are historically important, as trian-gulations are maximal planar graphs, and quadrangulations are maximal bipartite planar graphs. Hence, these two families often capture the diﬃculty of conjectures or algorithmic tasks on planar graphs and bipartite planar graphs.
Trees. A plane tree is a map with only one face, the outer face. Families of trees with refined conditions will be considered in Chapter 3.
Eulerian maps. A map is called Eulerian iﬀ all its vertices have even degree.
Loops and multiple edges are allowed.
Triangulated maps. A triangulated map is a loopless map such that all faces have degree 3. A triangulation is a map with no loop nor multiple edge and such that all faces have degree 3. Triangulations are also called maximal plane graphs because any edge addition breaks planarity. A triangulation of the k-gon is a map with no loop nor multiple edge and with an outer face of degree k and all inner faces of degree 3. A triangulation T of the k-gon is said to be irreducible if the interior of any 3-cycle is a face, i.e, there is no filled 3-cycle. Notice that k > 3 unless T is reduced to the triangle. A lot of attention in this thesis will be devoted to irreducible triangulations of the 4-gon, which we shortly call irreducible triangulations.
Bicolored maps. Bipartite maps are maps whose vertices can be partitioned into black and white vertices, with the property that any pair of adjacent vertices have diﬀerent colors. A bipartite map endowed with such a bicoloration is called a bicolored map. It is easily shown that bipartite maps are exactly maps with all faces of even degree. Moreover, the bicoloration of vertices is unique up to the color of the first vertex. Rooted bipartite maps will always be endowed with their unique bicoloration such that the origin of the root is black.
Quadrangulated maps. Quadrangulated maps are maps with all faces of degree 4. Notice that such maps are bipartite, so that they have no loops. Quadrangu-lations are quadrangulated maps with no multiple edges. Quadrangulations are also called maximal bipartite plane graphs because any edge addition either breaks bipartiteness or planarity. A separating 4-cycle of a quadrangulation is a 4-cycle C such that neither the interior nor the exterior of C is a face. A quadrangulation is called irreducible if it has no separating 4-cycle. For k ≥ 3, a quadrangulated dissection of the 2k-gon —shortly called dissection— is a map with outer face of degree 2k and all inner faces of degree 4. A dissection is said to be irreducible if the interior of any 4-cycle is a face. Notice that the definition is simpler than for quadrangulations, since the outer cycle is not a 4-cycle (hence, the exterior of a 4-cycle can not be a face). A lot of attention will be devoted to irreducible dissec-tions of the hexagon, which are of great interest for the algorithmic treatment of 3-connected maps.
k-connected maps. A map is called k-connected if at least k vertices (and their incident edges) have to be removed to disconnect the map; in addition the map must have at least k vertices, loops are forbidden if k > 1, and multiple edges are forbidden if k > 2. It is easily shown that a quadrangulation is 2-connected, a triangulation is 3-connected, and a triangulation is 4-connected iﬀ the interior of any 3-cycle—except the outer one—is a face. Notice that the characterisation of 4-connected triangulations is very close to the condition of irreducibility, except that the outer 3-cycle can be filled in a 4-connected triangulation. This link will be used in Chapter 3 to study 4-connected triangulations from irreducible triangulations.

READ Controls on overpressure evolution during the gravitacional collapse of the Amazon deepsea fan

Correspondences between families of maps

There exist several simple correspondences between families of maps. We recall here the duality map-ping and the angular mapping, which will be intensively used.

Duality

The dual of a map M is the map M ∗ having one vertex vf in each face f of M , two vertices vf and vf ′ being adjacent in M ∗ iﬀ the faces f and f ′ are adjacent in M , i.e., there exists an edge having f and f ′ on each side; see Figure 2 for an example. Each edge e ∈ M gives rise to exactly one edge e∗ ∈ M ∗, which crosses e at a vertex ve. The map obtained by superimposing M and M ∗ is called the derived map of M . The vertices of M ′ corresponding to intersections of an edge with its dual edge are called edge-vertices. Clearly each edge-vertex has degree 4 and each edge of the derived map either corresponds to a half-edge of M —these are called primal edges of M ′— or corresponds to a half-edge of M ∗ —these are called dual edges of M ′. A vertex of M ′ is said to be primal (dual ) if it belongs to M (to M ∗, respectively). The duality exchanges the number of vertices and faces, i.e., the dual of a map with i vertices, n edges, and j faces, is a map with j vertices, n edges, and i faces. It is also easily checked that the duality is involutive, i.e., (M ∗)∗ = M . If maps are rooted, the root of M ∗ is the dual edge of the root edge e of M , oriented from the left of e to the right of e. In its rooted version, the duality is involutive up to the orientation of the root. A nice property of duality is to preserve the connectivity degree up to order 3. The properties are summarized in the following theorem.
Theorem 1.1 (Duality). The families of connected, 2-connected, and 3-connected maps are stable under duality. The duality mapping is involutive and the parameters of a map M and of its dual map M ∗ satisfy the following correspondences:
vertex of M
face of M
edge of M
↔ face of M ∗,
↔ vertex of M ∗,
↔ edge of M ∗.

Angular mapping

There is a well known correspondence, due to Tutte, between quadrangular maps and unconstrained maps, which we call the angular mapping. Given a bicolored quadrangulated map Q, the primal map of Q is the map M whose vertices are the black vertices of Q, two black vertices being adjacent in M iﬀ they are incident to the same face of Q, see Figure 3. Notice that the same construction with white vertices instead of black vertices would give the dual map of M . Clearly, there is an edge of M for each face of Q. Conversely, Q is called the angular map of M , because each edge of Q corresponds to an angle of M . If Q is rooted, then the primal map also receives a root, which is chosen to be the edge following the root of Q in counterclockwise order around the root vertex of Q, see Figure 3. The angular mapping has a nice restriction to 2-connected and 3-connected maps. Indeed, the presence of a multiple edge in Q is equivalent to the presence of a separating vertex in M , and the presence of a separating 4-cycle in Q is equivalent to the presence of a separating pair of vertices in M [90]. The properties of the angular mapping are summarized in the following theorem.
Theorem 1.2 (Angular mapping). The angular mapping is a bijection between the following families of maps:
bicolored quadrangulated maps ↔ maps,
bicolored quadrangulations ↔ 2-connected maps,
bicolored irreducible quadrangulations ↔ 3-connected maps.
In its rooted version, the angular mapping is a bijection between the following families of rooted maps:
rooted quadranulated maps ↔ rooted maps,
rooted quadrangulations ↔ rooted 2-connected maps,
rooted irreducible quadrangulations ↔ rooted 3-connected maps.
The parameters of a quadrangulated map Q and of its primal map M satisfy the following correspondences:
edge of Q ↔ angle of M ,
black vertex of Q ↔ vertex of M ,
white vertex of Q ↔ face of M ,
face of Q ↔ edge of M .

The theory of α-orientations

Orientations with prescribed outdegree, the so-called α-orientations, are at the heart of all combinatorial structures to be presented later. A very elegant theory of these orientations has been developed by Propp [96], Ossona de Mendez [92], and Felsner [48]. The ideas can also be traced back to an earlier paper by Kuhler et al on the lattice properties of circulations in planar graphs [80]. This section recalls the main properties to be used later, in particular the lattice rules. First, let us recall the definition of distributive lattices.
Distributive lattices. A lattice is a partially ordered set (E, ≤) such that, for each pair (x, y) of elements of E, there exists a unique element x ∧ y and a unique element x ∨ y satisfying the conditions:
• x ∧ y ≤ x, x ∧ y ≤ y, and ∀z ∈ E, z ≤ x and z ≤ y implies z ≤ x ∧ y,
• x ∨ y ≥ x, x ∨ y ≥ y, and ∀z ∈ E, z ≥ x and z ≥ y implies z ≥ x ∨ y.
In other words, each pair admits a unique common lower element dominating all other common lower elements, and the same holds with common upper elements. The lattice is said to be distributive if the operators ∧ and ∨ are distributive with respect to each other, i.e., ∀(x, y, z), x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) and x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). We define a flip (flop) as the operation of moving from an element of the lattice to a lower (upper, respectively) covering element. The nice feature of distributive lattices is that, in most cases, moving from an element of the lattice to a covering lower (upper) element has a simple geometric interpretation, which we informally call a flip (flop, respectively). As we recall next, in the case of orientations of a plane graph with prescribed vertex outdegrees, the flip (flop) operation consists in reversing a clockwise circuit (counter-clockwise circuit, respectively).
Definition of α-orientations. Given a planar map M = (V, E) and a function α : V → N, an α-orientation is an orientation of the edges of M such that each vertex v has outdegree α(v). A function α : V → N such that M has at least one α-orientation is called feasible.
Conditions of existence. Given a function α : V → N, a necessary condition of existence of an α-orientation is clearly v∈V α(v) = |E|. There is a refinement of this condition to all subsets of V . For X ⊂ V , write δ(X, X) for the set of edges connecting a vertex in X and a vertex in X := V \X , and write E[X ] for the set of edges connecting two vertices in X . Then, in any α-orientation of M , the number of edges going from X to X has to be equal to OutX := v∈X α(v) − |E[X ]|. The cut condition states that, for any subset X ⊂ V , 0 ≤ OutX ≤ |δ(X, X )|. Clearly, the cut condition is a necessary condition of existence of an α-orientation. It is also a suﬃcient condition, as proved by induction on the number of edges [48].
Invariants. Given a planar map M = (V, E) and a fixed feasible function α : V → N for M , there are several properties shared by all α-orientations of M . We have seen that the number of edges going out of a subset X ⊂ V does not depend on the α-orientation, and satisfies 0 ≤ OutX ≤ |δ(X, X)|.
In the two extremal cases OutX = 0 and OutX = |δ(X, X )|, the edge cut (the set of edges connecting X and X) is called rigid. Clearly an edge belonging to a rigid edge-cut, called a rigid edge, has the same orientation in all α-orientations of M . Based on the cut condition, it is easily shown that the accessibility from a vertex v to a vertex v′ does not depend on the α-orientation. Hence the decomposition of M into strongly connected components does not depend on the α-orientation: the rigid edges are the edges connecting diﬀerent strongly connected components, and the non-rigid edges are the edges inside a strongly connected component. In particular, any non-rigid edge e belongs to an oriented circuit C. Reversing C yields another α-orientation where e has the reverse direction. Circuit reversion is the fundamental operation to navigate in the set of α-orientations of a planar map.
Essential circuits. Consider a planar map M endowed with an α-orientation. A circuit C is called chordal if there exists an oriented path P of edges inside C such that the two extremities of P are on C. As illustrated in Figure 4, reversing a chordal circuit can be done by reversing successively two smaller oriented cicuits, in the sense that the regions enclosed by these circuits are strictly included in the region enclosed by C. The circuits that are not chordal are called essential circuits. Hence, a circuit reversion can always be performed as a sequence of reversions of essential circuits. Notice that the status (essential or chordal) of a circuit C does not depend on the α-orientation. Indeed, C is essential iﬀ it is chordless and no vertex inside C is in the same strongly connected component as C. A cycle C appearing as an essential circuit in at least one α-orientation of M is called an essential cycle.
Definition. A flip (flop) is the operation of reversing a clockwise (counterclockwise, respectively) circuit.
Theorem 1.3 (Lattice property [48, 92, 96]). Given a planar map M and a feasible function α : V → N, the set of α-orientations of M endowed with the flip-flop operations is a distributive lattice.
Proof (Sketch). The idea is to associate a potential-vector to each α-orientation, so that the corresponding set of vectors is stable under minimum and maximum, hence is a distributive lattice for the min-max partial order. Define E as the set of essential cycles of M for the function α : V → N. Starting from an α-orientation X , it can be shown that the number of times an essential C cycle is flipped in a maximal flip-sequence is a finite number NX (C) not depending on the maximal flip-sequence [48]. As the number of essential cycles is finite, any flip-sequence terminates at an α-orientation X0, which has no clockwise circuit. In particular, this proves the existence of an α-orientation with no clockwise circuit. The uniqueness of such an orientation is also easily proved [48, Lem.1]. Then, the lattice structure relies on the following property; for two α-orientations X and X ′, there exists an α-orientation X ∧ X ′ and an α-orientation X ∨ X ′ such that NX∧X′ (C) = min(NX (C), NX′ (C)) and NX∨X′ (C) = max(NX (C), NX′ (C)) ∀C ∈ E. In other words, α-orientations of M are in bijection with a set of vectors of N|E| stable under minimum-maximum. The fact that such a vector-set is a distributive lattice is a folklore result. Finally it easily follows from the definition that the cover relation in the set of potential vectors corresponds to reversing the orientation of an essential circuit.
Applications. As discussed by Felsner [48], distributive lattices are well under-stood structures. Let us cite the fundamental theorem [105]: “a distributive lattice can be represented as the set of downward ideals of a partially ordered set”. This theorem is the formal general statement explaining why it is mostly easy to nav-igate in a distributive lattice using simple local operations. Accordingly, eﬃcient algorithms have been developed for uniform random generation [97] (using coupling from the past techniques) and exhaustive generation. An application of exhaustive generation to optimize a result of cartography will be given in Section 6.
The next sections are devoted to the presentation of combinatorial structures that characterise several families of planar maps, and have a natural formulation in terms of α-orientations. Let us mention a first example (not developed in this thesis); the set of spanning trees of a fixed rooted planar map M is in bijection with the set of α-orientations of the derived map M ′, for the function α equal to 1 for non-root primal and dual vertices, equal to 0 for the root vertex and v∞ (the dual vertex corresponding to the infinite face), and equal to 3 for edge-vertices. The bijection makes use of the fact that the edges dual to edges not in the spanning tree form a spanning tree of the dual map. Propp [96] and Felsner [48] characterise the flip operation directly on spanning trees.

Eulerian orientations

The first example of structure we investigate are Eulerian orientations. Let us first recall the definition of Eulerian circuits, which represent one of the first historical developments in graph theory. Given a graph G = (V, E), an Eulerian circuit C of G is a circuit traversing each edge of G exactly once. Eulerian circuits (and the similar notion of Eulerian path) have been first considered by Euler to give a negative answer to the classical K¨onigsberg problem (whether all the bridges of the city of K¨onigsberg can be traversed exactly once). Notice that the orientation of G induced by an Eulerian circuit is such that each vertex has same indegree as outdegree, in particular each vertex has even degree. A graph G with all vertices of even degree is called an Eulerian graph, and an orientation of the edges of G such that Indeg(v) = Outdeg(v) is called an Eulerian orientation.
Proposition 1.1 (Characterization (Folklore)). A graph admits an Eulerian orientation iﬀ it is Eulerian.
Proof. Clearly, a graph endowed with an Eulerian orientation is Eulerian. Con-versely, if a graph G is Eulerian, there exist classical algorithms to compute an Eulerian circuit for each connected component of G [54], inducing an Eulerian ori-entation. In fact, it is even simpler to compute directly an Eulerian orientation in a greedy way [103, Vol A, Sect6.4]. It can be shown that the problem of counting the number of Eulerian orienta-tions of a fixed Eulerian graph is diﬃcult, namely is #P-complete [87]. Neverthe-less, as observed in [96, 48], the set O of Eulerian orientations of a fixed Eulerian map has an explicit combinatorial structure.
Proposition 1.2 (Lattice structure [48, 96]). Given an Eulerian map M , the set of Eulerian orientations of M is a distributive lattice. The flip operation consists in reversing the orientation of a clockwise circuit delimiting a face.

Table of contents :

Introduction
Chapter 1. Combinatorial structures on planar maps
1. Planar maps
2. The theory of α-orientations
3. Eulerian orientations
4. Bipolar orientations
5. Schnyder woods
6. Transversal structures
Chapter 2. Efficient computation
1. Computation of α-orientations
2. Computing Eulerian orientations
3. Computing bipolar orientations
4. Computing Schnyder woods
5. Computing transversal structures
6. Appendix: proof of Theorem 2.1
Chapter 3. Bijective counting of maps
1. Bijections using root-accessible α-orientations
2. Bijections not depending on a root
3. Appendix: proof of Theorem 3.2
Chapter 4. Algorithmic applications
1. Counting planar maps
2. Coding planar maps
3. Random sampling of planar maps
4. Random sampling of planar graphs
Chapter 5. Straight-line drawing
1. Drawing using Schnyder woods
2. Drawing using transversal structures
3. Analysis of the drawing algorithms
4. Appendix: proof of Lemma 5.3
Conclusion et perspectives
Bibliography
Index