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.

READ THE INFLUENCE OF SPECIFIC EMOTIONS ON DECISION - MAKING AND BEHAVIOUR

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