It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T- of Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

We give an O(|V(G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graph G so that (i) no two segments have an interior point in common, (ii) two segments touch each other if and only if the corresponding vertices are adjacent. As a corollary, we obtain a strengthening of the following theorem of Ringel and Petrovič. The edges of any maximal bipartite plane graph G with outer face bwb'w' can be colored by two colors such that the color classes form spanning trees of G-b and G-b', respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new linear-time algorithm for constructing bipolar orientations of 2-connected plane graphs.

Acyclic orientations with exactly one source and one sink – the so-called bipolar orientations – arise in many graph algorithms and specially in graph drawing. The fundamental properties of these orientations are explored in terms of circuits, cocircuits and also in terms of “angles” in the planar case. Classical results get here new simple proofs; new results concern the extension of partial orientations, exhaustive enumerations, the existence of deletable and contractable edges, and continuous transitions between bipolar orientations.

Different areas of discrete mathematics lead to intrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensional N-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence, the Gauss code of the curve. Using the D-switch operation, we give a new simple characterization of these sequences and deduce a simple self-contained proof of Rosenstiehl's characterization.

We give here three simple linear time algorithms on planar graphs: a 4-connexity test for maximal planar graphs, an algorithm enumerating the triangles and a 3-connexity test. Although all these problems got already linear-time solutions, the presented algorithms are both simple and efficient. They are based on some new theoretical results.

We are concerned with two classes of planar graphs: maximal planar graphs (i.e. polyhedral graphs, triangulations) and maximal bipartite planar graphs (i.e. bipartite planar graphs with quadrilateral faces). For these graphs we consider constrained orientations with a constant indegree for the internal vertex set. We recall or prove new fundamental relations between these orientations, specific tree decompositions and bipolar orientations. In particular, these relations yield linear time computation algorithms. Using these orientations, we give a characterization of 4-connected maximal planar graphs and 3-connected planar graphs, which leads to simple line time algorithms.

We prove a very general representation theorem for posets and, as a corollary, deduce that any abstract simplicial complex S has a geometric realization in the Euclidean space of dimension P(S)-1, where P(S) is the Dushnik-Miller dimension of the face order of S.

We give a characterization of DFS cotree-critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE (Public Implementation of a Graph Algorithm Library and Editor) by the authors, and deduce an algorithm for finding a Kuratowski subdivision in a DFS cotree-critical graph.

It was known for years, in quantic physics especially, that the connected permutations (also called indecomposable permutations) of [0;n], i.e. those such that for any i<n there exists j>i with p(j)<i, are as many as the pointed hypermaps of size n, i.e. the transitive pairs (p,q) of permutations of a set of cardinality n with a distinguished element. The paper establishes a natural bijection between the two families. An encoding of maps follows.

We consider the colouring (or homomorphism) order C induced by all finite graphs and the existence of a homomorphism between them. This ordering may be seen as a lattice which is however far from being complete. In this paper we study bounds, suprema and maximal elements in C of some frequently studied classes of graphs (such as bounded degree, degenerated and classes determined by a finite set of forbidden subgraphs). We relate these extrema to cuts of subclasses K of C (cuts are finite sets which are comparable to every element of the class K). We determine all cuts for classes of degenerated graphs. For classes of bounded degree graphs this seems to be a very difficult problem which is also mirrored by the fact that these classes fail to have a supremum. We note a striking difference between undirected and oriented graphs. This is based on the recent work of C. Tardif and J. Nešetřil. Also minor closed classes are considered and we survey recent results obtained by authors. A bit surprisingly this order setting captures Hadwiger conjecture and suggests some new problems.

The dimension of a graph, that is the dimension of its incidence poset, became a major bridge between posets and graphs. Although allowing a nice characterization of planarity, this dimension badly behaves with respect to homomorphisms. We introduce the universal dimension of a graph G as the maximum dimension of a graph having a homomorphism to G. The universal dimension, which is clearly homomorphism monotone, is related to the existence of some balanced bicoloration of the vertices with respect to some realizer. Non trivial new results related to the original graph dimension are subsequently deduced from our study of universal dimension, including chromatic and extremal properties.

We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale which has been considered as the fastest implemented one [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25–36. Springer, 2004.]. We give here a simple full justification of the algorithm, based on a preliminary extended study of topological properties of DFS trees.

We define folding of a directed graph as a coloring (or a homomorphism) which is injective on all the down sets of a given depth. While in general foldings are as complicated as homomorphisms for some some classes they present an useful tool to study colorings and homomorphisms. Our main result yields for any proper minor closed class C a folding (of any prescribed depth) using a fixed number of colors. This in turn yields (for any C) the existence of a K_k-free graph which bounds all K_k-free graphs belonging to C. This has been conjectured and solved for k=3. Particularly, we prove (without using 4CT) the existence of a graph H with chromatic number at most 5 and clique number at most 4, such that any planar graph G is homomorphic to H. This is sandwiched between 4CT and 5CT for planar graphs and the general case has bearing to Hadwiger Conjecture.

We define the notions tree depth and upper chromatic number of a graph and show their relevance to local - global problems for graphs partitions. Particularly we show that the upper chromatic number coincides with the maximal function which can be locally demanded in a bounded coloring of any proper minor closed class of graphs. The rich interplay of these notions is applied to a solution of bounds of proper minor closed classes satisfying local conditions. Particularly, we prove the following result: For every graph M and a finite set F of connected graphs there exists a (universal) graph U = U(M, F) ∈Forb(F) such that any graph G ∈Forb(F) which does not have M as a minor satisfies G →U (i.e. is homomorphic to U). This solves the main open problem of restricted dualities for minor closed classes and as an application it yields the bounded chromatic number of exact odd powers of any graph in an arbitrary proper minor closed class. We also generalize the decomposition theorem of DeVos et al.

Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least 3 free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.

A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact family of segments and points. We deduce that any 4-connected 3-colorable plane graph is the contact graph of a family of segments and that any 4-colored planar graph without an induced C₄ using 4 colors is the intersection graph of a family of straight line segments.

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes).

Classes of graphs with bounded expansion are a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r(G). These classes are also characterized by the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. These results lead to several new linear time algorithms, such as an algorithm for counting all the isomorphs of a fixed graph in an input graph or an algorithm for checking whether there exists a subset of vertices of a priori bounded size such that the subgraph induced by this subset satisfies some arbirtrary but fixed first order sentence. We also show that for fixed p, computing the distances between two vertices up to distance p may be performed in constant time per query after a linear time preprocessing. We also show, extending several earlier results, that a class of graphs has sublinear separators if it has sub-exponential expansion. This result result is best possible in general.

We study restricted homomorphism dualities in the context of classes with bounded expansion. This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the “approximative version” of Hadwiger conjecture.

We characterize arrangeability and admissibility in terms of ∇₁(G) (Burr – Erdős conjecture relates to ∇₀(G)). This implies the linearity of the Ramsey number and bounded game chromatic number for some new classes of graphs.

A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality.

A vertex colouring of a graph G is nonrepetitive if for any path P = (v₁, v₂,...., v_2r) in G, the first half is coloured differently from the second half. The Thue choice number of G is the least integer l such that for every l-list assignment L of G, there exists a nonrepetitive L-colouring of G. We prove that for any positive integer l, there is a tree T with π_ch(T) > l. On the other hand, it is proved that if G' is a graph of maximum degree Δ, and G is obtained from G' by attaching to each vertex v of G' a graph of tree-depth at most d rooted at v, then π_ch(G)≤c(, d) for some constant c(Δ, d) depending only on Δ and d.

In this paper we define and analyze the nowhere dense classes of graphs. This notion is a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, classes with bounded expansion, to name just a few classes which are studied extensively in combinatorial and computer science contexts. In this paper we show that this concept leads to a classification of general classes of graphs and to the dichotomy between nowhere dense and somewhere dense classes. This classification is surprisingly stable as it can be expressed in terms of the most commonly used basic combinatorial parameters, such as the independence number α, the clique number ω, and the chromatic number χ. The remarkable stability of this notion and its robustness has a number of applications to mathematical logic, complexity of algorithms, and combinatorics. We also express the nowhere dense versus somewhere dense dichotomy in terms of edge densities as a trichotomy theorem.

We prove that the asymptotic logarithmic density of copies of a graph F in the graphs of a nowhere dense class C is integral and we determine the range of its possible values. This leads to a generalization of the Trichotomy theorem [26] and to a notion of degree of freedom of a graph F in a class C. This provides yet another formulation of the somewhere dense – nowhere dense classification. We obtain a structural result about the asymptotic shape of graphs with given degree of freedom.

We present a characterization of planarity based on Trémaux trees (i.e. DFS trees), from which we deduce a simple and efficient planarity test algorithm. We finally recall a theorem on “cotree critical non-planar graphs" which very much simplify the search of a Kuratowski subdivision in a non-planar graph.

In this paper, we propose a conjecture which says that every graph G with γ_f(G) ≤k+ (d)/(k+d+1) decomposes into k+1 forests, and one of the forests has maximum degree at most d. We prove two special cases of this conjecture: If G is a graph with fractional arboricity at most (43, then G decomposes into a forest and a matching. If G is a graph with fractional arboricity at most (32, then G decomposes into a forest and a linear forest. In particular, every planar graph of girth at least 8 decomposes into a forest and a matching, and every planar graph of girth at least 6 decomposes into a forest and a linear forest. This improves earlier results concerning decomposition of planar graphs. We give examples to show that there are planar graphs of girth 7 which does not decompose into a forest and a matching, and there are planar graphs of girth 5 which does not decompose into a forest and a linear forest. We also show that the bound in the conjecture above is sharp, i.e., for any ε> 0, there is a graph G with γ_f(G) < k+ (d)/(k+d+1) +ε, and yet G cannot be decomposed into k+1 forests, with one of them having maximum degree at most d.)/())/()

The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.

Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erdös-Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed d>0, there exists a class with bounded expansion, such that a random graph of order n and edge probability d/n asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class.

The n-th Fiedler value of a class of graphs C is the maximum second eigenvalue λ₂(G) of a graph G∈C with n vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the n-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

The arboricity of a graph G is the minimum number of colors needed to color the edges of G so that every cycle gets at least two colors. Given a positive integer p, we define the generalized p-arboricity _p(G) of a graph G as the minimum number of colors needed to color the edges of a multigraph G in such a way that every cycle C gets at least min(|C|,p+1) colors. In the particular case where G has girth at least p+1, _p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.

In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar result for the oriented chromatic number, from which follows in particular that graphs of large girth excluding a minor have oriented chromatic number at most 5, and for the pth chromatic number χ_p, from which follows in particular that graphs G of large girth excluding a minor have χ_p(G)≤p+2.

The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree-depth. In this paper we survey results related to this concept and particularly explain how these graphs are used to decompose and construct more complex graphs and structures. In more technical terms we survey some of the properties and applications of low tree-depth decomposition of graphs.

Scott proved in 1997 that for any tree T, every graph with bounded clique number which does not contain any subdivision of T as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if T is replaced by any graph H. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of Erdős). This shows that Scott's conjecture is false whenever H is obtained from a non-planar graph by subdividing every edge at least once. It remains interesting to decide which graphs H satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from K₄ by subdividing every edge at least once. We also prove that if G is a 2-connected multigraph with no vertex intersecting every cycle of G, then any graph obtained from G by subdividing every edge at least twice is a counterexample to Scott's conjecture.

In this note we characterize, within the framework of the theory of finite set, those categories of graphs that are algebraic universal in the sense that every concrete category fully embeds in them. The proof of the characterization is based on the sparse–dense dichotomy and its model theoretic equivalent.

We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing CONGEST_BC model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms.

In this paper we present a novel approach to graph (and structural) limits based on model theory and analysis. The role of Stone and Gelfand dualities is displayed prominently and leads to a general theory, which we believe is naturally emerging. This approach covers all the particular examples of structural convergence and it put the whole in new context. As an application, it leads to new intermediate examples of structural convergence and to a “grand conjecture” dealing with sparse graphs. We survey the recent developments.

We discuss the notion of structural sparsity and how it relates to the nowhere dense/somewhere dense dichotomy introduced by the authors for classes of graphs. This will be the occasion of surveying the numerous facets of this dichotomy, as well as its connections to several concepts like stability, independence, VC-dimension, regularity partitions, entropy, class speed, low tree-depth decomposition, quasi-wideness, neighborhood covering, subgraph statistics, etc. as well as algorithmic complexity issues like fixed parameter tractability of first-order model checking.

A strongly polynomial sequence of graphs (G_n) is a sequence (G_n)_n&isin;ℕ of finite graphs such that, for every graph F, the number of homomorphisms from F to G_n is a fixed polynomial function of n (depending on F). For example, (K_n) is strongly polynomial since the number of homomorphisms from F to K_n is the chromatic polynomial of F evaluated at n. In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Nešetřil, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found, leading to analogues of the chromatic polynomial for fractional colourings and acyclic colourings, to choose two interesting examples. Many graph polynomials, such as the Tutte polynomial and independence polynomial, are determined by strongly polynomial sequences of graphs. We give a new model-theoretic method of constructing strongly polynomial sequences of graphs that uses interpretation schemes of graphs in more general relational structures. This surprisingly easy yet general method encompasses all previous constructions and produces many more. We conjecture that, under mild assumptions, all strongly polynomial sequences of graphs can be produced by the general method of quantifier-free interpretation of graphs in certain basic relational structures (essentially disjoint unions of transitive tournaments with added unary relations). We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree.

The study of limits of graphs led to elegant limiting structures for sparse and dense graphs. This has been unified and generalized by authors in a more setting combining analytic tools and model theory to FO-limits (and X-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.

The notion of left convergent sequences of graphs introduced by Lovász et al. (in relation with homomorphism densities for fixed patterns and Szemerédi's regularity lemma) got increasingly studied over the past 10 years. Recently, Nešetřil and Ossona de Mendez introduced a general framework for convergence of sequences of structures. In particular, the authors introduced the notion of QF-convergence, which is a natural generalization of left-convergence. In this paper, we initiate study of QF-convergence for structures with functional symbols by focusing on the particular case of tree semi-lattices. We fully characterize the limit objects and give an application to the study of left convergence of m-partite cographs, a generalization of cographs.

The generalised colouring numbers _r(G) and _r(G) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications.

In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r-colouring number _r and a polynomial bound for the weak r-colouring number _r. In particular, we show that if G excludes K_t as a minor, for some fixed t≥4, then _r(G)≤t-12(2r+1) and _r(G)≤r+t-2t-2⋅(t-3)(2r+1)∈ (r^t-1).

In the case of graphs G of bounded genus g, we improve the bounds to _r(G)≤(2g+3)(2r+1) (and even _r(G)≤5r+1 if g=0, if G is planar) and _r(G)≤(2g+r+22)(2r+1).

The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way.

In this paper we consider a simple algebraic structure — sets with a single endofunction. We shall see that from the point of view of structural limits, even this simplest case is both interesting and difficult. Nevertheless we obtain the shape of limit objects in the full generality, and we prove the inverse theorem in the case of quantifier-free limits.

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed: (1) If a FO-convergent sequence of graphs is residual, that is if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit. (2) A monotone class of graphs C has the property that every FO-convergent sequence of graphs from C has a modeling limit if and only if C is nowhere dense, that is if and only if for each integer p there is N(p) such that no graph in C contains the pth subdivision of a complete graph on N(p) vertices as a subgraph. In this paper we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy.

Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no K_t+1-minor can be t-coloured so that each colour class induces asubgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.

The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end we introduced, in a 2012 conference paper, the notion of shrub-depth of a graph class which is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ω levels of the MSO1 transduction hierarchy of simple graphs.

Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every h ≥1 and every ε> 0, posets of height at most h with n elements and whose cover graphs are in the class have dimension O(n^ε).

Based on methods of structural convergence we provide a unifying view of local-global convergence, fitting to model theory and analysis. The general approach outlined here provides a possibility to extend the theory of local-global convergence to graphs with unbounded degrees. As an application, we extend previous results on continuous clustering of local convergent sequences and prove the existence of modeling quasi-limits for local-global convergent sequences of nowhere dense graphs.

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

The Hall ratio of a graph G is the maximum of |V(H)|/α(H) over all subgraphs H of G. Clearly, the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromatic number is upper bounded by a function of the Hall ratio. We answer this question in negative, by showing two results of independent interest regarding 1-subdivisions (the 1-subdivision of a graph is obtained by subdividing each edge exactly once).

For every c>0, every graph of sufficiently large average degree contains as a subgraph the 1-subdivision of a graph of fractional chromatic number at least c. For every d>0, there exists a graph G of averge degree at least d such that every graph whose 1-subdivision appears as a subgraph of G has Hall ratio at most 18.

We also discuss the consequences of these results in the context of graph classes with bounded expansion.

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this paper we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

Szemerédi's Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as “gentle” classes.

We prove that if G is a sparse graph — it belongs to a fixed class of bounded expansion C — and d∈N is fixed, then the dth power of G can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.

Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths – a result that shows a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes. The structural results we obtain are the following. 1) The number of unlabeled graphs of order n with linear rank-width at most r is at most [(2^r+1)(r+1)!2^r23^r+1]ⁿ 2) Graphs with linear rankwidth at most r are linearly χ-bounded. Actually, they have bounded c-chromatic number, meaning that they can be colored with f(r) colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family F of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in F. From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most r are first-order transductions of linear orders. This result could also be derived from Colcombet's theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth. 2) For a class C with bounded linear rankwidth the following conditions are equivalent: a) C is stable, b) C excludes some half-graph as a semi-induced subgraph, c) C is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.

Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of nowhere dense class). The theory of sparsity was initially built on the notion of shallow minors and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.

In this paper, we follow a similar path, where shallow vertex minors replace shallow minors. In this setting, we provide a neat characterization of stable / dependent hereditary classes of graphs: A hereditary class of graphs C is dependent if and only if it does not contain all permutation graphs and, for each integer r, it excludes some split interval graph as a depth-r vertex minor; it is stable if and only if, for each integer r, it excludes some half-graph as a depth-r vertex minor.

A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors. We extend this preservation result to binary structures and get, as a direct consequence, that bounded depth shallow vertex minors of graphs with bounded twin-width have bounded twin-width.

Regular orientations, that is orientations such that almost all the vertices have the same indegree, relates many combinatorial and topological properties, such as arboricity, page number, and planarity. These orientations are a basic tool in solving combinatorial problems that preserve topological properties. Planar augmentations are a simple example of such problems.

The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence. C.F. Gauss conjectured that such sequences could be characterized by their interlacement properties. This conjecture was proved by P. Rosenstiehl in 1976. We shall give here a simple self-contained proof of his characterization. This new proof relies on the D-switch operation.

We show that an abstract simplicial complex S may be realized on (d-1)-dimensional space, where d=P(S) is the order dimension (Dushnik-Miller dimension) of the face poset of S.

We define here the reduced genus of a multigraph as the minimum genus of a hypergraph having the same adjacencies with the same multiplicities. Through a study of embedded hypergraphs, we obtain new bounds on the coloring number, clique number and point arboricity of simple graphs of a given reduced genus. We present some new related problems on graph coloring and graph representation.

Drawing combinatorial structures is a new challenge aimed to a better control of data in industry and in business as well. Speaking of graph we often understand map since a rotation system of edges around the vertices is specified by the context or by choice of the data structures. Search is the crucial step in the process of drawing. Depth-First Search has generated in the past well known algorithms for planarity testing, map transformation, graph drawing. Breadth-First Search on the counterpart was rather neglected and appears to be the right tool for coding and drawing maps. A bijection is proposed here, between the pointed maps with m edges and the connected involutions on {0,1,...,2m+1}.

We present a simple linear time algorithm finding a Kuratowski subdivision in a DFS cotree critical graphs, based on recent theoretical results. For sake of clarity, we shall outline the proofs of the Theorem we make use of. This algorithm is the last part of the two step linear time Kuratowski finding algorithm implemented in PIGALE (“Public Implementation of a Graph Algorithm Library and Editor”, freely available at http://pigale.sourceforge.org).

Topic Maps have been introduced to interchangeably represent information about the structure of information resources used to define topics, and the relationships between topics. Graphs and hypergraphs have been introduced in discrete mathematics for a similar reason. Industrial needs related to Topic Maps not only rely on their representations in a data structure, but also deals with new complex information extraction requests, like Navigation, Structure Analysis, Minimal Cut search, etc. The adapted paradigm seems to be the one of a combinatorial hypermap, which has been introduced some decades ago. This paper presents this combinatorial object, associated data structures and algorithmic considerations about it. Topological graph theory is shown to be the right mathematical and algorithmic tool to handle Topic Maps efficiently.

Topic Maps have been developed in order to represent the structures of relationships between subjects, independently of resources documenting them, and to allow standard representation and interoperability of such structures. The ISO 13250 XTM specification have provided a robust syntactic XML representation allowing processing and interchange of topic maps. But topic maps have so far suffered from a lack of formal description, or conceptual model. We propose here such a model, based on the mathematical notions of hypergraph and connexity. This model addresses the critical issue of topic map organization in semantic layers, and provides ways to check semantic consistency of topic maps. Moreover, it seems generic enough to be used as a foundation for other semantic standards, like RDF.

We give a characterization of DFS-cotree critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE

We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines.

The increasing importance of e-learning has been a boosting element for the emergence of Internet based education services. As we move into the information age, tremendous efforts are continuously made in the development of new Web Technologies for educational services, while meeting the human resource and economical expectations. This paper reports on the capabilities of Pliant as a flexible software tool for enhancing the development of e-Learning management systems, while meeting educational and software-oriented expectations. This paper reports on the capabilities of Pliant as a new software tool and Web-based technology dedicated for e-learning and distance learning purposes.

A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a family of segments and points. We deduce that any 4-connected 3-colorable plane graphs is the contact graphs of a family of segments and that any 4-colored planar graph without induced C₄ using 4 colors is the intersection graph of a family of straight line segments.

Classes of graphs with bounded expansion generalize both proper minor closed classes and classes with bounded degree. For any class with bounded expansion C and any integer p there exists a constant N(C,p) so that the vertex set of any graph G∈C may be partitioned into at most N(C,p) parts, any i≤p parts of them induce a subgraph of tree-width at most (i-1) (actually, of tree-depth at most i, what is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities. We give here a simple algorithm to compute such partitions and prove that if we restrict the input graph to some fixed class C with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed C and p). This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion. More generally, let φ be a first order logic sentence. We prove that any fixed graph property of type “∃X: (|X|≤p) ∧(G[X]⊧φ)” may be decided in linear time for input graphs in a fixed class with bounded expansion.

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇_r(G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and restricted homomorphism dualities.

Many representation theorems extend from planar graphs to planar hypergraphs. The authors proved in a previous paper that every planar graph has a representation by contact of triangles. We prove here that this representation result extend to planar linear hypergraphs. Although the graph proof was simple and led to a linear time drawing algorithm, the extension for hypergraphs needs more work. The proof we give here relies on a combinatorial characterization of those hypergraphs which are representable by contact of segments in the plane, We propose some possible generalization directions and open problems, related to the order dimension of the incidence posets of hypergraphs.

We present results of the recent research on sparse graphs and finite structures in the context of of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. The topics include: complexity of subgraph- and homomorphism- problems; model checking problems for first order formulas in special classes; property testing in sparse classes of structures. All these problems can be studied under the umbrella of classes of structures which are Nowhere Dense and in the context of Nowhere Dense – Somewhere Dense dichotomy. This dichotomy presents the classification of the general classes of structures which proves to be very robust and stable as it can be defined alternatively by most combinatorial extremal invariants as well as by algorithmic and logical terms. We give examples from logic, geometry and extremal graph theory. Finally we characterize the existence of all restricted dualities in terms of limit objects defined on the homomorphism order of graphs.

This paper surveys the recent research related to the structural properties of sparse graphs and general finite relational structures. We provide a classification of classes of finite relational structures which is defined by means of a sequence of derived classes (defined by local changes). The resulting classification is surprisingly robust and it leads to many equivalent formulations which play an important role in applications in model theory, algorithmic graph theory and structural theory. One of these equivalent formulations guarantees a quick test for a finite type decomposition in a few classes (called low tree depth decomposition). We give numerous examples from geometry and extremal graph theory and apply the result to dualities for special classes of graphs. Finally we characterize the existence of all restricted dualities in terms of limit objects induced by the convergence defined on the homomorphism order of graphs.

Recent characterization of those graphs for which coloured MSO₂ model checking is fast raised the interest in the graph invariant called tree-depth. Looking for a similar characterization for (coloured) MSO₁, we introduce the notion of shrub-depth of a graph class. To prove that MSO₁ model checking is fast for classes of bounded shrub-depth, we show that shrub-depth exactly characterizes the graph classes having interpretation in coloured trees of bounded height. We also show that a common extension of cographs and of graphs with bounded shrub-depth — m-partite cographs (which is still below clique-width) — is well quasi-ordered by the relation “is an induced subgraph of” and therefore allows polynomial time testing of hereditary properties.

We extend the general framework of structural limits from graphs and relational structures to finite structures (including function symbols). For perhaps the simplest model of this type — sets with single unary function — we determine limit objects with respect to the three main fragments of first order. In each of these cases we solve an analog of Aldous-Lyons conjecture. This builds on the experience gained when studying limits of sequences of trees.

Given finitely many polygonal obstacles O₁,...,O_k in the plane and a set P of points in general position and not in any obstacle, the visibility graph of P with obstacles O₁,...,O_k is the (geometric) graph with vertex set P, where two vertices are adjacent if the straight line segment joining them intersects no obstacle.

The obstacle number of a graph G is the smallest number k of polygonal obstacles O₁,...,O_k such that G is the visibility graph of a set of points with obstacles O₁,...,O_k. If G is planar, we define the planar obstacle number of G by further requiring that the visibility graph has no crossing edges (hence that it is a planar geometric drawing of G). In this paper, we prove that the maximum planar obstacle number of a planar graph of order n is n-3, the maximum being attained (in particular) by maximal bipartite planar graphs. This displays a significant difference with the standard obstacle number, as we prove that the obstacle number of every bipartite planar graph of order at least 3 is 1. This last result is a consequence of a similar statement for intersection graphs of straight line segments in two directions.

We provide a new constant factor approximation algorithm for the (connected) distance-r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance-r dominating set problem is currently known. Our algorithm can be implemented in the CONGEST BC model of distributed computing and uses O(r² logn) communication rounds. Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an r-neighborhood cover of radius 2r and overlap f(r) on every class of bounded expansion in O(r²logn) communication rounds for some function f. Finally, we show how to use the greater power of the LOCAL model to turn any distance-r dominating set into a constantly larger connected distance-r dominating set in 3r+1 rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al. gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the model, where the approximation ratio is only 6 times larger than that of Lenzen et al.'s algorithm.

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order (FO) transductions and the quasiorder they induce on infinite classes of finite graphs. Surprisingly, this quasiorder is very complex, though shaped by the locality properties of first-order logic. This contrasts with the conjectured simplicity of the monadic second order (MSO) transduction quasiorder. We first establish a local normal form for FO transductions, which is of independent interest. Then we prove that the quotient partial order is a bounded distributive join-semilattice, and that the subposet of additive classes is also a bounded distributive join-semilattice. The FO transduction quasiorder has a great expressive power, and many well studied class properties can be defined using it. We apply these structural properties to prove, among other results, that FO transductions of the class of paths are exactly perturbations of classes with bounded bandwidth, that the local variants of monadic stability and monadic dependence are equivalent to their (standard) non-local versions, and that the classes with pathwidth at most k form a strict hierarchy in the FO transduction quasiorder.

Given any bipartite planar graph G, one can assign vertical and horizontal segments to its vertices so that (a) no two of them have an interior point in common, (b) two segments have a point in common if and only if the corresponding vertices are adjacent in G.

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T- of Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

A family of Jordan arcs, such that two arcs are nowhere tangent, defines a hypergraph whose vertices are the arcs and whose edges are the intersection points. We shall say that the hypergraph has a strong intersection representation and, if each intersection point is interior to at most one arc, we shall say that the hypergraph has a strong contact representation. We first characterize those hypergraphs which have a strong contact representation and deduce some sufficient conditions for a simple planar graph to have a strong intersection representation. Then, using the Four Color Theorem, we prove that a large class of simple planar graphs have a strong intersection representation.

We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.

We prove that the vertex set of any twin-free multigraph G has an embedding into some point set P of some Euclidean space R^k, such that the automorphism group of G is isomorphic to the isometry group of R^k globally preserving P.

We show that pointed maps with m edges are in bijection with standard double occurrence words with (m+1) symbols.

We survey some of the recent results related to the study of sparse graphs using the nowhere dense - somewhere dense dichotomy. Particularly we extend known results related to property testing, sublinear expanders, Ramsey numbers and FO model checking. All this is done under the same umbrella of nowhere dense and bounded expansion classes in many of their incarnations. We concentrate on extremal (mostly graph theory) results leaving algorithmic and structural aspects to other occasions.

We address the problem of characterizing H-coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give several characterizations of a homomorphism dualities arising in a class of structure.

We consider mappings, which are structure consisting of a single function (and possibly some number of unary relations) and address the problem of approximating a continuous mapping by a finite mapping. This problem is the inverse problem of the construction of a continuous limit for first-order convergent sequences of finite mappings. We solve the approximation problem and, consequently, the full characterization of limit objects for mappings for first-order (i.e. FO) convergence and local (i.e. FO^local) convergence. This work can be seen both as a first step in the resolution of inverse problems (like Aldous-Lyons conjecture) and a strengthening of the classical decidability result for finite satisfiability in Rabin class (which consists of first-order logic with equality, one unary function, and an arbitrary number of monadic predicates). The proof involves model theory and analytic techniques.

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a fuzzy notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants. This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. This book is related to the material presented by the first author at ECM 1998 and ICM 2010.

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

PICTEL is an automatic schematic drawing software for aeronautic electrical circuits integrated into CATIA

Penelope is a software dedicated to the conception and simulation of warp-weft fabrics

This program is an automatic SADT diagram drawing software

Pliant project consists in the creation under GPL licence of a coherent and minimal software package including the base tools necessary for most users. These tools are gathered into a short source code thanks to a new language which allows to focus on what is pertinent, without preventing programmers to access any of the abstraction levels or to impose any exception to the general rules. Pliant project maybe accessed at http://fullpliant.org.

Pigale integrates a graph algorithm library written in C++ and a graph editor based on Qt and OpenGL libraries. This program is particularly intended for academic research on topological graphs. Pigale is available under GPL licence by FTP or CVS at http://sourceforge.net/projects/pigale/.

Ariane is a bibliographical administration software

The subject of this thesis is the concept of bipolar orientation of a 2-connected graph, that is an acyclic orientation with a unique source and a unique sink. The investigation starts with the abstraction of bipolar orientations in the framework of the regular oriented matroids, which is convenient field for the study of deletion, erasing and extension properties. The establishment of a perfect graph encoding any bipolar orientation of a regular matroid leads to a new characterization of graphic matroids. The planarity of a graph is then characterized in terms of the dimension of the edge partial order induced by a bipolar orientation. It is established that any two bipolar orientations of a 3-connected graph are connected by a sequence of bipolar orientations generated step by step by reversing exactly one edge. It is shown that in the case of planar graphs, there is a distributive lattice structure on the set of bipolar orientations. And the same structure holds for the 3-tree Schnyder decompositions of maximal planar graphs. In the final chapter, two representation theorems are proved: any planar graph may be represented as contact graph of families of triangles; any bipartite planar graph may be represented as contact graph of families of horizontal and vertical segments

The orientation of programming languages seems to follow two main directions: The first one corresponds to a seek of major companies to get more and more power over end users, while limiting their own responsibility in a kind of “democracy” under trusteeship. The other one is a quest for independence of the users expressed, for instance, in the free software movement. While the first tendency leads to a severe limitation of programmers' possibilities and to a uniformization of “personal” softwares restricted to “macro-softwares”, the needs of the second one for coherency might lead to the introduction of another kind of operating system responsible for a language-independent compilation, which we shall call a language operating system, allowing a new level of integration: language-level integration.