This page has been partly generated using bibtex2html.
Abstracts: Hide/Show/Selective Show.
[A1] 
H. de Fraysseix, P. Ossona de Mendez, and J. Pach.
Representation of planar graphs by segments.
In Intuitive Geometry, volume 63 of Colloquia Mathematica
Societatis János Bolyai, pages 109–117. NorthHolland, 1991.
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. 
[A2] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
On triangle contact graphs.
Combinatorics, Probability and Computing, 3:233–246, 1994.
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 Yshaped objects follow. Moreover, there is a onetoone mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees. 
[A3] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
Bipolar orientations revisited.
Discrete Applied Mathematics, 56:157–179, 1995.
[ DOI ]
Acyclic orientations with exactly one source and one sink – the socalled 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. 
[A4] 
H. de Fraysseix, P. Ossona de Mendez, and J. Pach.
A LeftFirst Search Algorithm for Planar Graphs.
Discrete & Computational Geometry, 13:459–468, 1995.
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 Gb and Gb', respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new lineartime algorithm for constructing bipolar orientations of 2connected plane graphs. 
[A5] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
On Triangle Contact Graphs.
In Combinatorics, Geometry and Probability: A Tribute
to Paul Erdős, pages 165–178. Cambridge University Press, 1997.
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 Yshaped objects follow. Moreover, there is a onetoone mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees. 
[A6] 
H. de Fraysseix and P. Ossona de Mendez.
Planarity and edge poset dimension.
European Journal of Combinatorics, 17:731–740, 1997.
[ DOI ]
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 2dimensional Nfree partial orders. We give also a characterization of planarity in terms of 2colorability of a graph and provide a short proof of a previous result on planar lattices. 
[A7] 
H. de Fraysseix and P. Ossona de Mendez.
On a Characterization of Gauss Codes.
Discrete & Computational Geometry, 22(2):287–295, 1999.
[ DOI ]
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 Dswitch operation, we give a new simple characterization of these sequences and deduce a simple selfcontained proof of Rosenstiehl's characterization. 
[A8] 
H. de Fraysseix and P. Ossona de Mendez.
Intersection Graphs of Jordan Arcs.
In Contemporary Trends in Discrete Mathematics,
volume 49 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science, pages 11–28.
DIMATIADIMACS, 1999.
Štiřin 1997 Proc.
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. 
[A9] 
H. de Fraysseix and P. Ossona de Mendez.
On topological aspects of orientations.
Discrete Mathematics, 229(13):57–72, 2001.
[ DOI ]
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 4connected maximal planar graphs and 3connected planar graphs, which leads to simple line time algorithms. 
[A10] 
H. de Fraysseix and P. Ossona de Mendez.
Connectivity of planar graphs.
Journal of Graph Algorithms and Applications, 5(5):93–105,
2001.
We give here three simple linear time algorithms on planar graphs: a 4connexity test for maximal planar graphs, an algorithm enumerating the triangles and a 3connexity test. Although all these problems got already lineartime solutions, the presented algorithms are both simple and efficient. They are based on some new theoretical results. 
[A11] 
P. Ossona de Mendez.
Realization of posets.
Journal of Graph Algorithms and Applications, 6(1):149–153,
2002.
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 DushnikMiller dimension of the face order of S. 
[A12] 
J. Nešetřil and P. Ossona de Mendez.
Colorings and homomorphisms of minor closed classes.
In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, The
GoodmanPollack Festschrift, volume 25 of Algorithms and
Combinatorics, pages 651–664. Discrete & Computational Geometry,
2003.
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. 
[A13] 
H. de Fraysseix and P. Ossona de Mendez.
On cotreecritical and DFS cotreecritical graphs.
Journal of Graph Algorithms and Applications, 7(4):411–427,
2003.
[ .pdf ]
We give a characterization of DFS cotreecritical 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 cotreecritical graph. 
[A14] 
P. Ossona de Mendez and P. Rosenstiehl.
Transitivity and connectivity of permutations.
Combinatorica, 24(3):487–502, 2004.
[ DOI ]
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. 
[A15]  P. Ossona de Mendez. Realization of posets. In Graph Algorithms and Applications 3, pages 149–153. World Scientific, 2004. 
[A16]  H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. In Graphs Algorithms and Applications 2. World Scientific, 2004. 
[A17] 
P. Ossona de Mendez and P. Rosenstiehl.
Homomorphism and dimension.
Combinatorics, Probability and Computing, 14(56):861–872,
2005.
[ DOI ]
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. 
[A18] 
J. Nešetřil and P. Ossona de Mendez.
Cuts and bounds.
Discrete Mathematics, Structural Combinatorics  Combinatorial
and Computational Aspects of Optimization, Topology and Algebra,
302(13):211–224, 2005.
[ DOI ]
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. 
[A19] 
P. Ossona de Mendez and P. Rosenstiehl.
Encoding pointed maps by double occurrence words.
In University of Piraeus, editor, Volume of essays in honour of
Professor Antonios C. Panayotopoulos, pages 701–712. Eptalofos, 2006.
We show that pointed maps with m edges are in bijection with standard double occurrence words with (m+1) symbols. 
[A20] 
J. Nešetřil and P. Ossona de Mendez.
Tree depth, subgraph coloring and homomorphism bounds.
European Journal of Combinatorics, 27(6):1022–1041, 2006.
[ DOI ]
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. 
[A21] 
J. Nešetřil and P. Ossona de Mendez.
Folding.
Journal of Combinatorial Theory, Series B, 96(5):730–739,
2006.
[ DOI ]
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. 
[A22] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
Depthfirst search and planarity.
International Journal of Foundations of Computer Science,
17(5):1017–1029, 2006.
Special Issue on Graph Drawing.
[ DOI ]
We present a simplified version of the DFSbased LeftRight 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 DFSbased 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. 
[A23] 
H. de Fraysseix and P. Ossona de Mendez.
Regular embeddings of multigraphs.
In M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, and
P. Valtr, editors, Topics in Discrete Mathematics, volume 26 of
Algorithms and Combinatorics, pages 553–563. SpringerVerlag, 2006.
Dedicated to Jarik Nešetřil on the occasion of his
60^{th} birthday.
We prove that the vertex set of any twinfree 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. 
[A24] 
H. de Fraysseix and P. Ossona de Mendez.
On representations by contact and intersection of segments.
Algorithmica, 47(4):453–463, 2007.
[ DOI ]
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 4connected 3colorable plane graph is the contact graph of a family of segments and that any 4colored planar graph without an induced C_{4} using 4 colors is the intersection graph of a family of straight line segments. 
[A25] 
H. de Fraysseix and P. Ossona de Mendez.
Barycentric systems and stretchability.
Discrete Applied Mathematics, 155(9):1079–1095, 2007.
[ DOI ]
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 noncrossing 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 pseudosegments is stretchable if and only if it is extendible. 
[A26] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion III. Restricted graph
homomorphism dualities.
European Journal of Combinatorics, 29(4):1012–1024, 2008.
[ DOI ]
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. 
[A27] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion II. Algorithmic aspects.
European Journal of Combinatorics, 29(3):777–791, 2008.
[ DOI ]
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 treewidth and low treedepth 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 subexponential expansion. This result result is best possible in general. 
[A28] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion I. Decompositions.
European Journal of Combinatorics, 29(3):760–776, 2008.
[ DOI ]
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 treewidth and low treedepth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes). 
[A29] 
J. Nešetřil and P. Ossona de Mendez.
Fraternal augmentations, arrangeability and linearly bounded Ramsey
numbers.
European Journal of Combinatorics, 30(7):1696–1703, 2009.
[ DOI ]
We characterize arrangeability and admissibility in terms of ∇_{1}(G) (Burr – Erdős conjecture relates to ∇_{0}(G)). This implies the linearity of the Ramsey number and bounded game chromatic number for some new classes of graphs. 
[A30] 
J. Nešetřil and P. Ossona de Mendez.
First order properties on nowhere dense structures.
The Journal of Symbolic Logic, 75(3):868–887, 2010.
[ DOI ]
A set A of vertices of a graph G is called dscattered in G if no two dneighborhoods of (distinct) vertices of A intersect. In other words, A is dscattered 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 quasiwide 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 widetype 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. 
[A31] 
J. Nešetřil and P. Ossona de Mendez.
Extremal problems for sparse graphs.
In I. Bárány and J. Solymosi, editors, An irregular mind
(Szemerédi is 70), volume 21 of Bolyai Society Mathematical
Studies, pages 447–490. Springer, 2010.
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. 
[A32] 
J. Nešetřil and P. Ossona de Mendez.
How many F's are there in G?
European Journal of Combinatorics, 32(7):1126–1141, 2011.
[ DOI ]
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 [33] 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. 
[A33] 
J. Nešetřil and P. Ossona de Mendez.
On nowhere dense graphs.
European Journal of Combinatorics, 32(4):600–617, 2011.
[ DOI ]
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. 
[A34] 
F. Fiorenzi, P. Ochem, P. Ossona de Mendez, and X. Zhu.
Thue choosability of trees.
Discrete Applied Mathematics, 159:2045–2049, 2011.
[ DOI ]
A vertex colouring of a graph G is nonrepetitive if for any path P = (v_{1}, v_{2},...., 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 llist assignment L of G, there exists a nonrepetitive Lcolouring 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 treedepth at most d rooted at v, then π_{ch}(G)≤c(, d) for some constant c(Δ, d) depending only on Δ and d. 
[A35] 
J. Nešetřil, P. Ossona de Mendez, and D.R. Wood.
Characterizations and examples of graph classes with bounded
expansion.
European Journal of Combinatorics, 33(3):350–373, 2012.
[ DOI ]
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 lineartime 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 socalled 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ösRé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 nonrepetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologicallyclosed class, while graphs with bounded crossing number are contained in a minorclosed class. 
[A36] 
J. Nešetřil and P. Ossona de Mendez.
A model theory approach to structural limits.
Commentationes Mathematicæ Universitatis Carolinæ,
53(4):581–603, 2012.
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.

[A37] 
M. Montassier, P. Ossona de Mendez, A. Raspaud, and X. Zhu.
Decomposing a graph into forests.
Journal of Combinatorial Theory, Series B, 102(1):38–52, 2012.
[ DOI ]
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.)/())/() 
[A38] 
H. de Fraysseix and P. Ossona de Mendez.
Planarity and Trémaux trees.
European Journal of Combinatorics, 33(3):279–293, 2012.
[ DOI ]
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 nonplanar graphs" which very much simplify the search of a Kuratowski subdivision in a nonplanar graph. 
[A39] 
J. Nešetřil and P. Ossona de Mendez.
A note on Fiedler value of classes with sublinear separators.
Linear Algebra and its Applications, 439:2216–2221, 2013.
[ DOI 
http ]
The nth Fiedler value of a class of graphs C is the maximum second eigenvalue λ_{2}(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 nth Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

[A40] 
J. Nešetřil, P. Ossona de Mendez, and X. Zhu.
Coloring edges with many colors in cycles.
Journal of Combinatorial Theory, Series B, 109:102–119, 2014.
[ DOI ]
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 parboricity _{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 pacyclic edge chromatic number of G. In this paper, we relate the generalized pacyclic edge chromatic numbers and the generalized parboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G. 
[A41] 
J. Nešetřil and P. Ossona de Mendez.
On low treedepth decompositions.
Graphs and Combinatorics, 31(6):1941–1963, 2015.
[ DOI ]
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 treedepth. 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 treedepth decomposition of graphs. 
[A42] 
J. Nešetřil and P. Ossona de Mendez.
A note on circular chromatic number of graphs with large girth and
similar problems.
Journal of Graph Theory, 80(4):268–276, 2015.
[ DOI ]
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. 
[A43] 
J. Nešetřil and P. Ossona de Mendez.
On firstorder definable colorings.
In J. Nešetřil and M. Pellegrini, editors, Geometry,
Structure and Randomness in Combinatorics, volume 18 of Publications of
the Scuola Normale Superiore, CRM Series, pages 99–122. Edizioni della
Normale, 2015.
We address the problem of characterizing Hcoloring problems that are firstorder 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.

[A44] 
J. Nešetřil and P. Ossona de Mendez.
Structural sparsity.
Uspekhi Matematicheskikh Nauk, 71(1):85–116, 2016.
(Russian Math. Surveys 71:1 79107).
[ DOI ]
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, VCdimension, regularity partitions, entropy, class speed, low treedepth decomposition, quasiwideness, neighborhood covering, subgraph statistics, etc. as well as algorithmic complexity issues like fixed parameter tractability of firstorder model checking. 
[A45] 
J. Nešetřil and P. Ossona de Mendez.
Firstorder limits, an analytical perspective.
European Journal of Combinatorics, 52 Part B:368–388, 2016.
[ DOI ]
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. 
[A46] 
J. Nešetřil and P. Ossona de Mendez.
Existence of modeling limits for sequences of sparse structures.
2016.
submitted.
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (G_{n})_{n∈ℕ} of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true. 
[A47] 
J. Nešetřil and P. Ossona de Mendez.
A distributed low treedepth decomposition algorithm for bounded
expansion classes.
Distributed Computing, 29(1):39–49, 2016.
[ DOI ]
We study the distributed low treedepth decomposition problem for graphs restricted to a bounded expansion class. Low treedepth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a lineartime 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 treedepth 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 messagepassing 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 treedepth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low treedepth decomposition linear time algorithm are used as a core procedure in several nontrivial linear time algorithms. We believe that, similarly, low treedepth decomposition could be at the heart of several nontrivial logarithmic time algorithms. 
[A48] 
J. Nešetřil and P. Ossona de Mendez.
Towards a characterization of universal categories.
Journal of Pure and Applied Algebra, 2016.
[ DOI ]
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (G_{n})_{n∈ℕ} of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true. 
[A49] 
J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez.
Restricted frame graphs and a conjecture of Scott.
Electronic Journal of Combinatorics, 23(1):#P1.30, 2016.
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 trianglefree 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 nonplanar 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_{4} by subdividing every edge at least once. We also prove that if G is a 2connected 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. 
[A50] 
A.J. Goodall, J. Nešetřil, and P. Ossona de Mendez.
Strongly polynomial sequences as interpretations.
Journal of Applied Logic, 18:129–149, May 2016.
[ DOI ]
A strongly polynomial sequence of graphs (G_{n}) is a sequence (G_{n})_{n∈ℕ} 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 modeltheoretic 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 quantifierfree 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. 
[A51] 
J. Nešetřil and P. Ossona de Mendez.
Modeling limits in hereditary classes: Reduction and application to
trees.
Electronic Journal of Combinatorics, 23(2):#P2.52, December
2016.
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 FOlimits (and Xlimits) 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. 
[A52] 
P. Ossona de Mendez, S. Oum, and D.R. Wood.
Defective colouring of graphs excluding a subgraph or minor.
Combinatorica, 2017.
accepted.
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3coloured 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 tcoloured 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 queuenumber, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor. 
[A53]  J. Nešetřil and P. Ossona de Mendez. Limits of mappings. European Journal of Combinatorics, 66:145–159, 2017. 
[A54] 
J. Nešetřil and P. Ossona de Mendez.
Cluster analysis of local convergent sequences of structures.
Random Structures & Algorithms, 51(4):674–728, 2017.
[ DOI ]
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. 
[A55] 
J. Nešetřil and P. Ossona de Mendez.
A unified approach to structural limits (with application to the
study of limits of graphs with bounded treedepth).
Memoirs of the American Mathematical Society, 2017.
accepted.
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.

[A56]  J. van den Heuvel, P. Ossona de Mendez, D. Quiroz, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European Journal of Combinatorics, 66:129–144, 2017. 
[A57] 
P. Charbit, L. Hosseini, and P. Ossona de Mendez.
Limits of structures and the example of treesemilattices.
Discrete Mathematics, 340:2589–2603, 2017.
[ DOI ]
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 QFconvergence, which is a natural generalization of leftconvergence. In this paper, we initiate study of QFconvergence for structures with functional symbols by focusing on the particular case of tree semilattices. We fully characterize the limit objects and give an application to the study of left convergence of mpartite cographs, a generalization of cographs.

[P1] 
H. de Fraysseix and P. Ossona de Mendez.
Regular Orientations, Arboricity and Augmentation.
In DIMACS International Workshop, Graph
Drawing 94, volume 894 of Lecture notes in Computer Science,
pages 111–118, 1995.
[ DOI ]
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. 
[P2] 
H. de Fraysseix and P. Ossona de Mendez.
A short proof of a Gauss problem.
In G. DiBattista, editor, Graph Drawing
Proceedings, volume 1353 of Lecture Notes in Computer
Science, pages 230–235. Springer, 1997.
[ DOI ]
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 selfcontained proof of his characterization. This new proof relies on the Dswitch operation. 
[P3] 
P. Ossona de Mendez.
The Reduced Genus of a Multigraph.
In STACS 99, volume 1563 of Lecture notes in
Computer Science, pages 16–31. Springer, 1999.
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. 
[P4] 
P. Ossona de Mendez.
Geometric Realization of Simplicial Complexes.
In J. Kratochvil, editor, Graph Drawing, volume 1731 of
Lecture Notes in Computer Science, pages 323–332. Springer,
1999.
We show that an abstract simplicial complex S may be realized on (d1)dimensional space, where d=P(S) is the order dimension (DushnikMiller dimension) of the face poset of S. 
[P5] 
P. Ossona de Mendez and P. Rosenstiehl.
What search for graph drawing.
In IIIS, editor, World Multiconference on
Systemics, Cybernetics and Informatics, volume XI, pages 125–130,
2000.
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. DepthFirst Search has generated in the past well known algorithms for planarity testing, map transformation, graph drawing. BreadthFirst 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}. 
[P6] 
P. Ossona de Mendez.
Combinatorial hypermaps vs topic maps.
In XML Europe 2001, 2001.
[ .html ]
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. 
[P7] 
H. de Fraysseix and P. Ossona de Mendez.
An algorithm to find a Kuratowski subdivision in DFS cotree
critical graphs.
In Edy Try Baskoro, editor, Proceedings of the Twelfth
Australasian Workshop on Combinatorial Algorithms (AWOCA 2000),
pages 98–105, Indonesia, 2001. Institut Teknologi Bandung.
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). 
[P8] 
H. de Fraysseix and P. Ossona de Mendez.
A characterization of DFS cotree critical graphs.
In Graph Drawing, volume 2265 of Lecture notes in
Computer Science, pages 84–95, 2002.
We give a characterization of DFScotree critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE 
[P9] 
P. Auillans, P. Ossona de Mendez, P. Rosenstiehl, and B. Vatant.
A formal model for topic maps.
In Ian Horrocks and James Hendler, editors, The Seamntic Web 
ISWC 2002, volume 2342 of Lecture notes in Computer Science,
pages 69–83, 2002.
[ http ]
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. 
[P10] 
P. Ossona de Mendez, M.V. Santos, and I. Woungang.
Pliant: more than a programming language, a flexible elearning tool.
In World Conference on Educational Multimedia, Hypermedia and
Telecommunications (EDMEDIA), volume 2004 issue 1, pages 505–510, 2004.
[ http ]
The increasing importance of elearning 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 eLearning management systems, while meeting educational and softwareoriented expectations. This paper reports on the capabilities of Pliant as a new software tool and Webbased technology dedicated for elearning and distance learning purposes. 
[P11] 
H. de Fraysseix and P. Ossona de Mendez.
Stretching of Jordan arc contact systems.
In Graph Drawing, volume 2912 of Lecture Notes in
Computer Science, pages 71–85. Springer Verlag, 2004.
[ DOI ]
We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudolines. 
[P12] 
H. de Fraysseix and P. Ossona de Mendez.
Contact and intersection representations.
In J. Pach, editor, Graph Drawing 2004, volume 3383 of
Lecture Notes in Computer Science, pages 217–227. Springer Verlag,
2005.
[ DOI ]
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 4connected 3colorable plane graphs is the contact graphs of a family of segments and that any 4colored planar graph without induced C_{4} using 4 colors is the intersection graph of a family of straight line segments. 
[P13] 
J. Nešetřil and P. Ossona de Mendez.
Linear time low treewidth partitions and algorithmic consequences.
In STOC'06. Proceedings of the 38^{th} Annual
ACM Symposium on Theory of Computing, pages 391–400. ACM Press, 2006.
[ DOI ]
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 treewidth at most (i1) (actually, of treedepth 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. 
[P14] 
J. Nešetřil and P. Ossona de Mendez.
Fraternal augmentations of graphs, coloration and minors.
In Proceedings of the Sixth CzechSlovak International Symposium
on Combinatorics, Graph Theory, Algorithms and Applications, volume 28 of
Electronic Notes in Discrete Mathematics, pages 223–230, 2007.
[ DOI ]
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 treewidth colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and restricted homomorphism dualities. 
[P15] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
Representation of planar hypergraphs by contacts of triangles.
In Proceedings of Graph Drawing 2007, volume 4875/2008 of
Lecture Notes in Computer Science, pages 125–136. Springer, 2008.
[ DOI ]
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. 
[P16] 
J. Nešetřil and P. Ossona de Mendez.
From sparse graphs to nowhere dense structures: Decompositions,
independence, dualities and limits.
In European Congress of Mathematics, pages 135–165. European
Mathematical Society, 2010.
[ DOI ]
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. 
[P17] 
J. Nešetřil and P. Ossona de Mendez.
Sparse combinatorial structures: Classification and applications.
In R. Bhatia and A. Pal, editors, Proceedings of the
International Congress of Mathematicians 2010 (ICM 2010), volume IV, pages
2502–2529, Hyderabad, India, 2010. World Scientific.
[ .html ]
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. 
[P18] 
R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek,
P. Ossona de Mendez, and R. Ramadurai.
When trees grow low: Shrubs and fast MSO_{1}.
In MFCS 2012, volume 7464 of Lecture Notes in Computer
Science, pages 419–430. SpringerVerlag, 2012.
Recent characterization of those graphs for which coloured MSO_{2} model checking is fast raised the interest in the graph invariant called treedepth. Looking for a similar characterization for (coloured) MSO_{1}, we introduce the notion of shrubdepth of a graph class. To prove that MSO_{1} model checking is fast for classes of bounded shrubdepth, we show that shrubdepth 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 shrubdepth — mpartite cographs (which is still below cliquewidth) — is well quasiordered by the relation “is an induced subgraph of” and therefore allows polynomial time testing of hereditary properties.

[P19]  J. van den Heuvel, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. Electronic Notes in Discrete Mathematics, 49:523 – 530, 2015. [ DOI ] 
[P20] 
J. Nešetřil and P. Ossona de Mendez.
Structural limits and approximations of mappings.
Electronic Notes in Discrete Mathematics, 49:531–539, 2015.
[ DOI ]
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 AldousLyons conjecture. This builds on the experience gained when studying limits of sequences of trees. 
[P21] 
J. Gimbel, P. Ossona de Mendez, and P. Valtr.
Obstacle numbers of planar graphs.
In Proceedings of the 25th Symposium on Graph Drawing, Lecture
Notes in Computer Science. Springer, 2017.
accepted.
Given finitely many polygonal obstacles O_{1},...,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_{1},...,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.

[B1]  P. Ossona de Mendez. Graphes et Applications 2 (Traité IC2, série informatique et systèmes d'information), chapter 4. Représentations des graphes, pages 129–160. Hermès, 2007. 
[B2]  J. Nešetřil and P. Ossona de Mendez. Structural properties of sparse graphs. In Martin Grötschel and Gyula O.H. Katona, editors, Building Bridges Between Mathematics and Computer Science, volume 19 of Bolyai Society Mathematical Studies, pages 369–426. Springer, 2008. 
[B3] 
J. Nešetřil and P. Ossona de Mendez.
Sparsity (Graphs, Structures, and Algorithms), volume 28 of
Algorithms and Combinatorics.
Springer, 2012.
465 pages.
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. 
[B4]  H. de Fraysseix and P. Ossona de Mendez. Handbook of Graph Drawing and Visualization, chapter 19 (PIGALE), pages 599–620. Discrete Mathematics and Its Applications. CRC Press, 2013. 
[L1] 
H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.
PICTEL.
Industrial Software, 1984.
PICTEL is an automatic schematic drawing software for aeronautic electrical circuits integrated into CATIA 
[L2] 
H. de Fraysseix and P. Ossona de Mendez.
Penelope.
Industrial Software, 1990.
Penelope is a software dedicated to the conception and simulation of warpweft fabrics 
[L3] 
P. Chicourrat, H. de Fraysseix, and P. Ossona de Mendez.
A hierarchical diagram drawing software.
Industrial Software, 1997.
This program is an automatic SADT diagram drawing software 
[L4] 
P. Ossona de Mendez and H. Tonneau.
Pliant project.
Free Software (GPL licence), 1999.
[ http ]
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. 
[L5] 
H. de Fraysseix and P. Ossona de Mendez.
PIGALE: Public Implementation of a Graph Algorithm
Library and Editor.
Free Software (GPL licence), 2002.
[ http ]
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/. 
[L6] 
H. de Fraysseix, A. Joly, and P. Ossona de Mendez.
Ariane.
Software, 2003.
Ariane is a bibliographical administration software 
[D1]  P. Ossona de Mendez. Systèmes Mémoires Accessibles par leur Adresses ou leur Contenu. Brevet 82.07 777, 1982. 
[D2]  G.Th. Guilbaud, E. Coumet, P. Ossona de Mendez, and P. Rosenstiehl. Mathématique Sociale (Série “Savoir et Mémoire”). Video; Direction : M. Ferro, Réalisation : P. Gauge, 1993. AREHESS , Paris. 
[D3] 
P. Ossona de Mendez.
Orientations bipolaires.
PhD thesis, Ecole des Hautes Etudes en Sciences Sociales,
Paris, 1994.
The subject of this thesis is the concept of bipolar orientation of a 2connected 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 3connected 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 3tree 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 
[D4]  P. Ossona de Mendez. Théorie des Graphes: Epopée et Aventures, 1996. 
[D5]  P. Ossona de Mendez. La société de la virtualité. Liquidation Totale, (1):29–31, 2001. 
[D6]  M. de Mendez, P. Ossona de Mendez, M.V. Santos, and H. Tonneau. Pliant documentation initiative. Online documentation, 2001. [ http ] 
[D7]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Knowledge epublishing tools CRAFT199970979 IST 2000 52033 6.36.4 deliverable. confidential report, European Community, 2003. 108 pages. 
[D8] 
P. Ossona de Mendez and H. Tonneau.
The future of programming languages.
Software 2.0, (100):56–58, April 2003.
in Polish.
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 “macrosoftwares”, the needs of the second one for coherency might lead to the introduction of another kind of operating system responsible for a languageindependent compilation, which we shall call a language operating system, allowing a new level of integration: languagelevel integration. 
[D9]  AEOLUS. Structural properties of overlay computers: State of the art survey and algorithmic solutions. D1.1.1, project IPFP6015964 of EEC, 2006. (section 4 by P. Ossona de Mendez and J. Nešetřil). [ .pdf ] 
[D10]  P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer. Preface. In P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer, editors, The International Conference on Topological and Geometric Graph Theory, volume 31 of Electronic Notes in Discrete Mathematics, pages 1–4. Elsevier, 2008. [ DOI ] 
[D11]  F. Demangeon and P. Ossona de Mendez. Kyudo: The way of the bow. In P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer, editors, The International Conference on Topological and Geometric Graph Theory, volume 31 of Electronic Notes in Discrete Mathematics, page 17. Elsevier, 2008. Poem. [ DOI ] 
[D12]  L. Lovász, J. Nešetřil, P. Ossona de Mendez, and A. Schrijver. Preface. European Journal of Combinatorics, 32(7):951–953, 2011. Homomorphism and Limits special issue. 
[D13]  A. Machí, J. Nešetřil, P. Ossona de Mendez, and J.L. Ramírez Alfonsín. Preface. European Journal of Combinatorics, 33(3):277–278, 2012. Topological and Geometric Graph Theory special issue. [ DOI ] 
[D14]  P. Pajot. Le prix Abel recompense un spécialiste des mathématiques discrètes. La Recherche, pages 18–19, Juin 2012. (interview de P. Ossona de Mendez au sujet d'Endre Szemerédi). 
[D15]  P. Ossona de Mendez. Du théorème de Ramsey à la conjecture d'Erd os–Hajnal (1). Images des Mathématiques, September 2017. [ .html ] 
[D16]  P. Ossona de Mendez. Du théorème de Ramsey à la conjecture d'Erd os–Hajnal (2). Images des Mathématiques, December 2017. [ .html ] 
[ArXiv1]  J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion III. restricted dualities. arXiv:math/0508325 [math.CO], 2005. 
[ArXiv2]  J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. arXiv:math/0508324 [math.CO], 2005. 
[ArXiv3]  J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. decompositions. arXiv:math/0508323 [math.CO], 2005. 
[ArXiv4]  H. de Fraysseix, P. Rosenstiehl, and P. Ossona de Mendez. Trémaux trees and planarity. arXiv:math/0610935 [math.CO], 2006. 
[ArXiv5]  H. de Fraysseix and P. Ossona de Mendez. Regular embeddings of multigraphs. arXiv:math/0610937 [math.CO], 2006. 
[ArXiv6]  J. Nešetřil, P. Ossona de Mendez, and D.R. Wood. Characterisations and examples of graph classes with bounded expansion. arXiv:0902.3265 [math.CO], 2009. 
[ArXiv7]  J. Nešetřil, P. Ossona de Mendez, and X. Zhu. Colouring edges with many colours in cycles. arXiv:1108.1616 [math.CO], 2011. 
[ArXiv8] 
J. Nešetřil and P. Ossona de Mendez.
A note on Fiedler value of classes with sublinear separators.
HAL, August 2012.
[ http ]
The nth Fiedler value of a class of graphs C is the maximum second eigenvalue λ_{2}(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 nth Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

[ArXiv9]  J. Nešetřil and P. Ossona de Mendez. A model theory approach to structural limits. arXiv:1303.2865 [math.CO], 2013. 
[ArXiv10] 
J. Nešetřil and P. Ossona de Mendez.
A unified approach to structural limits (with application to the
study of limits of graphs with bounded treedepth).
arXiv:1303.6471v2 [math.CO], October 2013.
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.

[ArXiv11]  J. Nešetřil and P. Ossona de Mendez. Modeling limits in hereditary classes: Reduction and application to trees. arXiv:1312.0441 [math.CO], December 2013. 
[ArXiv12]  J. Nešetřil and P. Ossona de Mendez. On low treedepth decompositions. arXiv:1412.1581v1 [math.CO], 2014. 
[ArXiv13]  J. Nešetřil and P. Ossona de Mendez. A note on circular chromatic number of graphs with large girth and similar problems. arXiv:1402.3142 [math.CO], 2014. 
[ArXiv14]  A.J. Goodall, J. Nešetřil, and P. Ossona de Mendez. Strongly polynomial sequences as interpretations. arXiv:1405.2449 [math.CO], May 2014. 
[ArXiv15] 
J. Nešetřil and P. Ossona de Mendez.
On firstorder definable colorings.
arXiv:1403.1995v2 [math.CO], June 2014.
We address the problem of characterizing Hcoloring problems that are firstorder 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.

[ArXiv16]  J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. arXiv:1510.07788 [math.CO], 2015. 
[ArXiv17]  J. Nešetřil and P. Ossona de Mendez. Firstorder limits, an analytical perspective. arXiv:1503.07627 [math.CO], 2015. 
[ArXiv18] 
P. Charbit, L. Hosseini, and P. Ossona de Mendez.
Limits of structures and the example of treesemilattices.
arXiv:1505.03037 [math.CO], 2015.
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 QFconvergence, which is a natural generalization of leftconvergence. In this paper, we initiate study of QFconvergence for structures with functional symbols by focusing on the particular case of tree semilattices. We fully characterize the limit objects and give an application to the study of left convergence of mpartite cographs, a generalization of cographs.

[ArXiv19] 
P. Ossona de Mendez, S. Oum, and D.R. Wood.
Defective colouring of graphs excluding a subgraph or minor.
arXiv:1611.09060 [math.CO], 2016.
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3coloured 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 tcoloured 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 queuenumber, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor. 
[ArXiv20]  J. Nešetřil and P. Ossona de Mendez. Existence of modeling limits for sequences of sparse structures. arXiv:1608.00146 [math.CO], 2016. 
[ArXiv21]  J. Nešetřil and P. Ossona de Mendez. Limits of mappings. arXiv:1602.07147 [math.CO], 2016. 
[ArXiv22]  J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. arXiv:1608.01112 [math.CT], 2016. 
[ArXiv23] 
L. Hosseini and P. Ossona de Mendez.
Treeable graphings are local limits of finite graphs.
arXiv:1601.05580 [math.CO], 2016.
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (G_{n})_{n∈ℕ} of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true. 
[ArXiv24]  J. van den Heuvel, P. Ossona de Mendez, D. Quiroz, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. arXiv:1602.09052 [math.CO], 2016. 
[ArXiv25]  J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez. Restricted frame graphs and a conjecture of Scott. arXiv:1406.0338v2 [math.CO], 2016. 
[ArXiv26] 
G. Joret, P. Micek, P. Ossona de Mendez, and V. Wiechert.
Nowhere dense graph classes and dimension.
arXiv:1708.05424v1[math.CO], 2017.
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^{ε}).

[ArXiv27] 
S. Kreutzer, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz.
Algorithmic properties of sparse digraphs.
arxiv:1707.01701 [cs.DM], 2017.
The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs. We show that red many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion classes. More specifically, we show that the directed Steiner tree problem is fixedparameter tractable on any class of directed bounded expansion parameterized by the number k of nonterminals plus the maximal diameter s of a strongly connected component in the subgraph induced by the terminals. Our result strongly generalizes a result of Jones et al., who proved that the problem is fixed parameter tractable on digraphs of bounded degeneracy if the set of terminals is required to be acyclic. We furthermore prove that for every integer r≥1, the distancer dominating set problem can be approximated up to a factor O(logk) and the connected distancer dominating set problem can be approximated up to a factor O(k⋅logk) on any class of directed bounded expansion, where k denotes the size of an optimal solution. If furthermore, the class is nowhere crownful, we are able to compute a polynomial kernel for distancer dominating sets. Polynomial kernels for this problem were not known to exist on any other existing digraph measure for sparse classes.

[ArXiv28] 
R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek,
and P. Ossona de Mendez.
Shrubdepth: Capturing height of dense graphs.
arxiv:1707.00359 [cs.LO], 2017.
The recent increase of interest in the graph invariant called treedepth 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 shrubdepth of a graph class which is related to the established notion of cliquewidth in a similar way as treedepth is related to treewidth. Since then shrubdepth has been successfully used in several research papers. Here we provide an indepth review of the definition and basic properties of shrubdepth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrubdepth to give a characterization of the lower ω levels of the MSO1 transduction hierarchy of simple graphs.

[ArXiv29] 
J. Gimbel, P. Ossona de Mendez, and P. Valtr.
Obstacle numbers of planar graphs.
arXiv:1706.06992 [math.CO], 2017.
Given finitely many polygonal obstacles O_{1},...,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_{1},...,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.

[ArXiv30]  S.A. Amiri, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Distributed domination on graph classes of bounded expansion. arXiv:1702.02848 [cs.DC], 2017. 
[KAM1]  H. de Fraysseix and P. Ossona de Mendez. A short proof of a Gauss problem. Technical Report 97358, KAMDIMATIA Series, 1997. 
[KAM2]  H. de Fraysseix and P. Ossona de Mendez. Stretchability of Jordan Arc Contact Systems. Technical Report 98387, KAMDIMATIA Series, 1998. 
[KAM3]  J. Nešetřil and P. Ossona de Mendez. Colorings and homomorphisms of minor closed classes. Technical Report 2001523, KAMDIMATIA Series, 2001. 
[KAM4]  J. Nešetřil and P. Ossona de Mendez. Folding. Technical Report 2002089, KAMDIMATIA Series, 2002. 
[KAM5]  J. Nešetřil and P. Ossona de Mendez. Cuts and bounds. Technical Report 2002097, KAMDIMATIA Series, 2002. 
[KAM6]  J. Nešetřil and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds. Technical Report 2004656, KAMDIMATIA Series, 2004. 
[KAM7]  P. Ossona de Mendez and P. Rosenstiehl. Encoding pointed maps by double occurrence words. Technical Report 2005752, KAMDIMATIA Series, 2005. 
[KAM8] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion III. Restricted
dualities.
Technical Report 2005741, KAMDIMATIA Series,
2005.
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. 
[KAM9] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion II. Algorithmic aspects.
Technical Report 2005740, KAMDIMATIA Series,
2005.
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 treewidth and low treedepth 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 subexponential expansion. This result result is best possible in general. 
[KAM10] 
J. Nešetřil and P. Ossona de Mendez.
Grad and classes with bounded expansion I. Decompositions.
Technical Report 2005739, KAMDIMATIA Series,
2005.
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 treewidth and low treedepth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes). 
[KAM11]  J. Nešetřil and P. Ossona de Mendez. Linear time low treewidth partitions and consequences. Technical Report 2006763, KAMDIMATIA Series, 2006. 
[KAM12]  J. Nešetřil and P. Ossona de Mendez. Induced matchings and induced paths in graphs. Technical Report 2007810, KAMDIMATIA Series, 2007. 
[KAM13]  J. Nešetřil and P. Ossona de Mendez. Structural properties of sparse graphs. Technical Report 2008863, KAMDIMATIA Series, 2008. 
[KAM14]  J. Nešetřil and P. Ossona de Mendez. First order properties on nowhere dense structures. Technical Report 2008865, KAMDIMATIA Series, 2008. 
[KAM15]  J. Nešetřil, P. Ossona de Mendez, and D.R. Wood. Characterisations and examples of graph classes with bounded expansion. Technical Report 2009909, KAMDIMATIA Series, 2009. [ .pdf ] 
[KAM16]  J. Nešetřil and P. Ossona de Mendez. On nowhere dense graphs. Technical Report 2009928, KAMDIMATIA Series, 2009. [ .pdf ] 
[KAM17]  J. Nešetřil, P. Ossona de Mendez, and X. Zhu. Colouring edges with many colours in cycles. Technical Report 20111008, KAMDIMATIA Series, 2011. [ .pdf ] 
[KAM18] 
J. Nešetřil and P. Ossona de Mendez.
A unified approach to structural limits (with application to the
study of limits of graphs with bounded treedepth).
Technical Report 2013573, KAMDIMATIA Series,
2013.
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.

[KAM19] 
J. Nešetřil and P. Ossona de Mendez.
On firstorder definable colorings.
Technical Report 2014609, IUUKCEITI Series, 2014.
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.

[KAM20] 
J. Nešetřil and P. Ossona de Mendez.
A note on circular chromatic number of graphs with large girth and
similar problems.
Technical Report 2014606, IUUKCEITI Series, 2014.
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.

[KAM21] 
J. Nešetřil and P. Ossona de Mendez.
A distributed low treedepth decomposition algorithm for bounded
expansion classes.
Technical Report 2015623, IUUKCEITI Series, 2015.
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.

[KAM22]  J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. Technical Report 2016643, IUUKCEITI Series, 2016. 
[KAM23]  J. Nešetřil and P. Ossona de Mendez. Structural sparsity. Technical Report 2016642, IUUKCEITI Series, 2016. 
[KAM24]  J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. Technical Report 2016641, IUUKCEITI Series, 2016. 
[ALCOM1]  M. Bousset, H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Envahir sans encercler l'ennemi. Technical report, ALCOM 9072, 1990. 
[ALCOM2]  M. Bousset, H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Posters on the automatic generation of layouts of technological networks. Technical report, ALCOM 9162, 1991. 
[ALCOM3]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Partial orders and orientation. ALCOM journal, 1992. 
[ALCOM4]  P. Ossona de Mendez. Partial angle assignments compatible with an orientation of a plane graph. Technical report, ALCOM II027, 1993. 
[ALCOM5]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Technical report, ALCOM II025, 1993. 
[ALCOM6]  H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. Technical report, ALCOM II031, 1993. 
[ALCOM7]  H. de Fraysseix, P. Ossona de Mendez, and J. Pach. A streamlined depthfirst search algorithm revisited. Technical report, ALCOMII030, 1993. 
[ALCOM8]  H. de Fraysseix and P. Ossona de Mendez. Planarity and edge poset dimension. Technical report, ALCOM II024, 1993. 
[ALCOM9]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Technical report, ALCOM report, 1994. 
[CAMS1]  H. de Fraysseix and P. Ossona de Mendez. On intersection graphs of Jordan arcs. Technical Report 146, CAMS, 1997. 
[CAMS2]  H. de Fraysseix and P. Ossona de Mendez. A short proof of a Gauss problem. Technical Report 145, CAMS, 1997. 
[CAMS3] 
P. Chicourrat, H. de Fraysseix, and P. Ossona de Mendez.
A hierarchical diagram drawing software.
Technical Report 147, CAMS, 1997.
Intermediate between texts and pictures, diagrams are a natural presentation scheme for computerhuman interface. For instance, hierarchical diagrams are an usual tool for engineering and documentation of complex systems. Although the handmade documentation is restricted to particular views of the system, an automatic diagram drawer allows the production of querydriven functional subsystems. 
[CAMS4]  H. de Fraysseix and P. Ossona de Mendez. On topological aspects of orientations. Technical Report 158, CAMS, 1998. 
[CAMS5] 
P. Ossona de Mendez and P. Rosenstiehl.
Connected permutations and hypermaps.
Technical Report 183, CAMS, 1999.
[ .dvi.gz ]
A link is developed between the orbits of a bigenerated permutation group and the components of a permutation p over an interval of N, these components corresponding to subintervals fixed by p. Several bijections are established between combinatorial families whose equicardinality were considered as mysterious by the literature so far. A coding of pointed maps and hypermaps follows. 
[CAMS6]  P. Ossona de Mendez. The reduced genus of a multigraph. Technical Report 174, CAMS, 1999. 
[CAMS7]  P. Ossona de Mendez. Geometric realization of simplicial complexes. Technical Report 178, CAMS, 1999. 
[CAMS8] 
P. Ossona de Mendez.
3colorability and contacts of segments.
Technical Report 171, CAMS, 1999.
Using a previous result on planar graph representation, we shall prove that vertex 3colorability is NPcomplete for contact graphs of segments even if no 3 segments may share a contact point, if the segments lye in 4directions and if the representation is given. 
[CAMS9]  M. Las Vergnas and P. Ossona de Mendez. On barycentric representation of graphs. Technical Report 182, CAMS, 1999. 
[CAMS10]  H. de Fraysseix and P. Ossona de Mendez. Stretchability of Jordan arc contact systems. Technical Report 172, CAMS, 1999. 
[CAMS11]  H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. Technical Report 173, CAMS, 1999. 
[r1]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. In Fifth FrancoJapanese Days on Combinatorics and Optimization, 1992. abstract. 
[r2] 
P. Ossona de Mendez.
The Plane Bipolar Orientations' Lattice.
In Sixth FrancoJapanese Days on Combinatorics and
Optimization, 1993.
abstract.
Given a biconnected graph G and an oriented edge e=(s,t) of G, a bipolar orientation based on the orientation of e (or ebipolar orientation of G) is an acyclic orientation of the edges of G having s as a unique source and t as a unique sink. Bipolar orientations are closely related to connexity and planarity. They have been extensively used to perform graph drawing of planar graphs, upward drawings and testing graph planarity. In the planar case, the angle graphe A(G) of G is defined as the vertex/face adjacency graph related to an embedding of G. Then, the ebipolar orientations of G are in bijection with the edge 2colorations of A(G) satisfying local conditions. From the 2coloration corresponding to an ebipolar orientation, the 2coloration corresponding to any other ebipolar orientation may be obtained by inverting the edge coloration over alternating cycles. An edge 2coloration of A(G) is equivalent to an orientation of the edges of A(G). When considering this orientation, alternating cycles of A(G) correspond to oriented circuits. The transformation from one ebipolar orientation O into another ebipolar orientation O' corresponds (in A(G)) to the inversion of a circuit. This circuit may be expressed as the sum of clockwise oriented faces of A(G) using integer coefficients. All or part of these coefficients might be negative integers. If all of them are positive, O is said to be smaller than O'. If the graph is 3connected, the so defined partial order is a distributive lattice on the ebipolar orientations' set of a plane graph G. That means that two uncomparable ebipolar orientations O and O' have an infimum O∧O' (a greatest ebipolar orientation smaller than both O and O') and a supremum O∨O'. This lattice is distributive as the infimum and supremum operators are distributive with one another. Moreover, the minimum and maximum ebipolar orientations of the lattice may be expressed using a very simple lineartime algorithm. The Hasse diagram of the lattice, that is the graph whose vertices are the ebipolar orientations of G and whose (oriented) edges correspond to the immediatesucessor relation, is the adjacency graph of the ebipolar orientations of G (two orientations being adjacent if they differ by the orientation of an unique edge) with an appropriate orientation. 
[r3]  P. Ossona de Mendez. On Lattice Structures induced by Orientations. In Proc. of Graph Drawing '93, pages 33–34, 1993. abstract. 
[r4]  H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. In proc. of Graph Drawing '93, pages 37–38, 1993. abstract. 
[r5]  H. de Fraysseix and P. Ossona de Mendez. New problems and conjectures. In Prague Midsummer Combinatorial Workshop, volume 93254, pages 8–10, 1993. abstract. 
[r6]  H. de Fraysseix and P. Ossona de Mendez. On Regular Orientations. In Prague Midsummer Combinatorial Workshop, pages 9–13, 1994. abstract. 
[r7]  H. de Fraysseix and P. Ossona de Mendez. Some augmentation problems. In Effiziente Algorithmen, volume 34/1994, page 11, 1994. abstract. 
[r8]  P. Ossona de Mendez. Representation of Hypergraphs by Contact of Segments. In Conférence Internationale “Graphe et Combinatoire”, 1995. abstract. 
[r9]  H. de Fraysseix and P. Ossona de Mendez. 9 Problems from Paris Group as presented by Hubert and Patrice – Selected problems from the Atelier de Taxiplanie. In Prague Midsummer Combinatorial Workshop, pages 28–31, 1995. abstract. 
[r10]  H. de Fraysseix and P. Ossona de Mendez. Intersection graphs of Jordan arcs. In Discrete and Computational Geometry : Ten Years Later, page 14, 1995. 
[r11]  H. de Fraysseix, T. Matsumoto, P. Ossona de Mendez, and P. Rosenstiehl. Regular Orientations and Graph Drawing. In Third Slovenian International Conference in Graph Theory, pages 12–13, 1995. abstract. 
[r12]  H. de Fraysseix and P. Ossona de Mendez. Distributive Lattices on Planar Graphs. In T. Nishizeki, R. Tamassia, and D. Wagner, editors, Graph Algorithms and Applications, volume 219 of DagsthulSeminarReport, page 30, 1998. abstract. 
[r13]  H. Crapo, P. Ossona de Mendez, and P. Rosenstiehl. Permutation coding of maps on surfaces. In János Bolyai Mathematical Society, editor, Paul Erdös and his Mathematics, abstracts of invited talks, pages 53–54, 1999. 
[r14]  P. Ossona de Mendez and P. Rosenstiehl. Coding properties of BreadthFirst Search orderings. In 6ème Colloque International de Théorie des Graphes, volume 5 of Electronic Notes in Discrete Mathematics, pages 253–255, 2000. [ DOI ] 
[r15]  H. de Fraysseix and P. Ossona de Mendez. Lower bounds on sets supporting Fáry drawings. In O. Pangrac, editor, Graph Theory Day V, volume 2001539 of KAM Series, pages 35–37, 2001. [ .ps ] 
[r16]  P. Ossona de Mendez and P. Rosenstiehl. Connected permutations and hypermaps. In Prague Midsummer Combinatorial Workshop VIII, number 2002561 in KAMDIMATIA Series, pages 13–18, 2002. abstract. 
[r17]  P. Ossona de Mendez and P. Rosenstiehl. Balanced bicoloration, homomorphism and graph dimension. In M. Bálek, editor, Prague Midsummer Combinatorial Workshop X, number 2004682 in KAMDIMATIA Series, pages 47–53, 2004. abstract. 
[r18]  J. Nešetřil and P. Ossona de Mendez. How many colors may we require? In M. Mareš, editor, Prague Midsummer Combinatorial Workshop IX, number 2004686 in KAMDIMATIA Series, pages 27–30, 2004. abstract. 
[r19] 
J. Nešetřil and P. Ossona de Mendez.
The grad of a graph and classes with bounded expansion.
In A. Raspaud and O. Delmas, editors, 7^{th}
International Colloquium on Graph Theory, volume 22 of Electronic Notes
in Discrete Mathematics, pages 101–106. Elsevier, 2005.
[ DOI ]
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 treewidth colorings and homomorphism dualities. 
[r20] 
J. Nešetřil and P. Ossona de Mendez.
Aspects algorithmiques des classes d'expansion bornée.
In L. Esperet, editor, 7^{e} Journées Graphes
et Algorithmes, volume 1372–05, pages 55–58. LaBRI – Université
Bordeaux I, 2005.
[ www: ]
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 treewidth and low treedepth 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. Moreover, classes with expansion bounded by a subexponential function have sublinear separators. 
[r21]  J. Nešetřil and P. Ossona de Mendez. Low treedepth partitions of classes with bounded expansion. In J. Kára, editor, Midsummer Combinatorial Workshop 2005 and DIMACS, DIMATIA, Rényi Workshop 2005, volume 2006770 of KAM Series, pages 76–81, 2006. 
[r22]  J. Nešetřil and P. Ossona de Mendez. Finding high girth chromatic subgraphs in high chromatic sparse graphs. In M. Tesar, editor, Workshop on Coverings and Colorings 2009, volume 2009929 of KAMDIMATIA Series, pages 11–12, 2009. 
[r23]  J. Nešetřil and P. Ossona de Mendez. Counting homomorphisms to sparse graphs. In J. Nešetřil and A. Raspaud, editors, European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), volume 34, pages 393–397, 2009. [ DOI ] 