Nous prouvons que tout graphe plan peut être représenté par un système de triangles en contact, i.e. par une collection de disques triangulaires disjoints sauf en leur points de contact, tout point de contact étant le sommet d'exactement un triangle. Nous en déduisons des représentations par contacts d'objets en forme de T et de Y, respectivement. De plus, nous montrons que les représentations par contacts de triangles d'un graphe maximal planaire sont en bijection avec les décompositions de Schnyder du graphe en trois arbres.

Nous explicitons un algorithme en temps O(|V(G)|) assignant aux sommets d'un graphe biparti plan des sommets horizontaux et verticaux de telle sorte que (i) deux segments n'aient jamais de point interieur commun, (ii) deux segments aient un point commun si et seulement si les sommets correspondants sont adjacents dans G. Comme corollaire, nous obtenons un renforcement du théorème de Ringel and Petrovič: les arêtes de tout graphe maximal biparti plan G de face extérieure bwb'w' peuvent être coloriées en deux couleurs, de telle sorte que les classes forme des arbres couvrants de G-b et G-b', respectivement. De plus, une telle coloration peut être calculée en temps linéaire. Notre méthode est basée sur un nouvel algorithme en temps linéaire d'orientation bipolaire d'un graphe 2-connexe plan.

Les orientations acycliques possédant une seule source et un seul puits – connues sous le nom d'orientations bipolaires – apparaissent dans nombre d'algorithmes de graphes et spécialement dans ceux de tracé. Les propriétés fondamentales de ces orientations sont explorées, en termes de circuits, de cocircuits, mais aussi d'“angles” dans le cas planaire. Nous donnons des preuves orignales simples des résulats classiques; les nouveaux résultats concernent l'extension d'une orientation partielle, l'existence d'arêtes effa`a�ables et/ou contractibles, et les transitions continues entre orientations bipolaires.

Les différents domaines des mathématiques discrètes ont apporté des caractérisation intrinsèquement différentes de la planarité. Celle ci peut être exprimée en termes topologiques, combinatoires, algébriques ou par les propriétés d'arbres de recherche. Plus récemment, Schnyder a relié la planarité avec la théorie des ordres partiels. Les orientations acycliques et l'ordre partiel associé sur les arêtes amène une nouvelle caractérisation de la planarité qui décrit, de plus, tous les plongements planaires possibles. Nous démontrons que les graphes plans bipolairement orientés sont en bijection avec les ordres partiels N-free de dimension 2. Nous caractérisons également la planarité en termes de 2-colorabilité d'un graphe, et fournissons une preuve courte d'un précédent résultat sur les treillis planaires.

La traversée d'un courbe simple auto-sécante du plan ayant des points de multiplicité au plus deux définit une suite à double occurences, le code de Gauss de la courbe. En utilisant l'opération de “D-switch”, nous donnons une nouvelle caractérisation simple de ces séquences et en déduisons une preuve simple et auto-suffisante de la caractérisation de Rosenstiehl.

Nous donnons ici trois algorithmes simples en temps linéaire opérant sur les graphes planaires: un test de 4-connexité pour les graphes maximaux planaires, un algorithme énumérant les triangles et un test de 3-connexité. Bien que tous ces problèmes aient déjà re`a�u des solutions en temps linéaire, les algorithmes proposés présentent l'intérêt de la simplicité et de l'efficacité. Ces algorithmes sont basés sur de nouveaux résultats théoriques.

Nous étudions deux classes de graphes planaires: les graphes maximaux planaires (i.e. graphes polyhedraux, triangulations) et les graphes planaires bipartis maximaux (i.e. graphes bipartis planaires quadrangulés). Nous considérons les orientations de ces graphes possédant un degré entrant constant sur l'ensemble des sommets internes. Nous rappelons ou démontrons de nouvelles relations fondamentales entre ces orientations, des décompositions particulières en arbres et les orientations bipolaires. En particulier, ces relations engendrent des algorithmes en temps linéaire. Gr`a�ce à ces orientations, nous donnons de nouvelles caractérisations de la 4-connexité des graphes maximaux planaires et de la 3-connexité des graphes planaires induisant des algorithmes simples en temps linéaire.

Nous prouvons un théorème de représentation d'ordre partiel très général et, comme corollaire, déduisons que tout complexe simplicial abstrait S peut être réalisé géométriquement dans l'espace Euclidien de dimension (d-1), o`a� d=P(S) est la dimension de Dushnik-Miller de l'ordre partiel d'inclusion des faces de S.

Nous donnons une caractérisation des graphes DFS coarbre-critiques qui est central à l'algorithme en temps linéaire de recherche d'une configuration de Kuratowski dans un graphe non planaire mis en œuvre dans PIGALE (Public Implementation of a Graph Algorithm Library and Editor) par les auteurs, et en déduisons un algorithme de recherche d'une configuration de Kuratowski dans un graphe DFS coarbre-critique.

Il était connu depuis des années, spécialement en physique quantique, que les permutations connexes (également appelées permutations indécomposables) de [0;n], i.e. les permutations telles que, pour tout i<n, il existe j>i tel que p(j)<i, sont en nombre égal à celui des hypercartes pointées de taille n, i.e. que les paires transitives (p,q) de permutation sur un ensemble de cardinal n possédant un élément distingué. Cet article établit une bijection naturelle entre ces deux familles. Un codage des cartes s'ensuit.

Nous considérons l'ordre de coloration (ou d'homomorphisme) sur l'ensemble des graphes finis. Cet ordre peut être vu comme un treillis qui, néanmoins, est loin d'être complet. Dans cet article, nous étudions les bornes, les suprema et les éléments maximaux de certaines classes C fréquemment étudiées (graphes à degrés bornés, graphes dégénérés et graphes définis par un ensemble de mineurs exclus). Nous relions ces extrema aux antichaines de sous classes K de C. Nous déterminons toutes les antichaines de la classe des graphes dégénérés. En ce qui concerne les classes des graphes de degrés uniformément bornés, le problème semble particulièrement difficile, ainsi que le laissait présager le fait que ces classes n'ont pas de supremum. Nous notons une différence fondamentale de comportement entre graphes orientés et non orientés, à partir des travaux récents de C. Tardif et J. Nešetřil. Nous considérons également les classes fermées par mineurs et survolons des résultats récents obtenus par les auteurs. Cette approche s'avère étonnamment reliée à la conjecture de Hadwiger et suggère de nouveaux problèmes.

La dimension d'un graphe, c'est-à-dire la dimension de son ordre partiel d'incidence, s'est imposé comme étant un pont majeur entre ordres partiels et graphes. Quoique permettant une élégante caractérisation de la planarité, cette dimension se comporte mal avec les homomorphismes. Nous introduisons la dimension universelle d'un graphe G comme étant la dimension maximale d'un graphe ayant un homomorphisme vers G. La dimension universelle, qui est clairement homomorphisme monotone, est liée à l'existence de certaines bicolorations équilibrées des sommets au sein d'un réaliseur. De nouveaux résultats non triviaux reliant la dimension (standard) d'un graphe sont déduites de notre étude de la dimension universelle, concernant en particulier des propriétés chromatiques et extrémales.

Nous présentons une version simplifiée de l'algorithme de test de planarité Gauche-Droite (basé sur un parcours en profondeur) qui est mis en œuvre dans Pigale et a étćonsidéré comme le plus rapide actuellement [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25–36. Springer, 2004.]. Nous donnons une justification simple et compl`a�te de l'algorithme, basée sur une étude préliminaire des propriétés topologiques des arbres de DFS.

Nous définissons le repliement d'un graphe orienté comme étant une coloration (ou un homomorphisme) injective sur toute section finissante d'une certaine profondeur. Alors que les repliements généraux sont aussi complexes que les homomorphismes, ils représentent pour certaines classes un outil performant d'étude des homomorphismes et des colorations. Notre résultat principal affirme l'existence, pour toute classe propre C fermée par mineurs, d'un repliement (de profondeur prescrite) utilisant un nombre fixé de couleurs. Nous en déduisons l'existence, pour toute classe propre C fermée par mineur, d'un graphe sans K_k bornant tous les graphes sans K_k de C. Cette propriété avait été conjecturée et résolue dans un précédent article dans le cas particulier k=3. En particulier, nous prouvons (sans l'aide du théorème des quatre couleurs) l'existence d'un graphe H de nombre chromatique au plus 5 et de nombre de clique au plus 4, tel que tout graphe planaire soit homomorphique à H. Ce résultat est donc intermédiaire entre le théorème des quatre couleurs et le théorème des cinq couleurs. Le cas général semble lié à la conjecture de Hadwiger.

Nous d'efinissons les notions de profondeur d'arbre et nombre chromatique sup'erieur d'un graphe et montrons leurs pertinences aux ph'enom`a�nes local-global li'es aux partitions de graphe. En particulier, nous montrons que le nombre chromatique sup'erieur coincide avec la fonction maximale pouvant `a�tre localement exig'ee dans une coloration born'ee au sein d'une classe ferm'ee par mineurs. La forte inter-relation de ces notions trouve une application dans la d'etermination d'une borne pour les classes ferm'ees par mineurs satisfaisant des conditions locales. En particulier, nous prouvons le r'esulat suivant: Pour tout graphe M et tout ensemble fini F de graphes connexes, il existe un graphe (universel) U = U(M, F) ∈Forb(F) tel que tout graphe G ∈Forb(F) n'ayant pas M comme mineur satisfasse G →U (i.e. G est homomorphique `a� U). Cela r'esoud le principal probl`a�me ouvert conernant les dualit'es restreintes pour les classes ferm'ees par mineur; comme application, cela implique que les nombres chromatiques des puissance impaires exactes des graphes d'une classe propre ferm'ee par mineur sont born'es. Nous g'en'eralisons 'egalement le th'eor`a�me de d'ecomposition de DeVos et al.

À partir d'une résolution générale des systèmes barycentriques, nous proposons une généralisation du théorème de Tutte sur le tracé convexe des graphes planaires. Nous déduisons une caractérisation des couvertures de l'ensemble des arêtes d'un graphe planaires en chaînes non intersectantes rectifiables: un système de chaîne non intersectantes est rectifiable si et seulement si tout sous-système d'au moins deux chaînes possède au moins 3 sommets libres (sommets de la face extérieure du sous-graphe induit qui ne sont intérieurs à aucune des chaînes du sous système). Nous déduisons également qu'un système de contact de pseudo-segments est rectifiable si, et seulement si, il est extensible.

Nous donnons une condition n'ecessaire et suffisante pour qu'un graphe biparti connexe donn'e soit le graphe d'incidence d'une famille de contact de segments et de points. Nous d'eduisons que tout graphe 4-connexe 3-coloriable planaire est le graphe de contact d'une famille de segments et que tout graphe planaire 4-colori'e sans C₄ induit utilisant 4 couleurs est le graphe d'intersection d'une famille de segments.

Nous introduisons les classes de graphes d'expansion born'ee en g'en'eralisant les classes propres ferm'ees par mineurs et les classes de degr'e born'e. Ces classes sont d'efinies `a� partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rang r, ∇_r(G). Pour ces classes, nous prouvons l'existence de diff'erentes partitions, en particluier l'existence de partition induisant des graphes de faible tree-width et faible tree-depth. Nous g'en'eralisons et simplifions diff'erents resultats pr'ec'edents (obtenus pour les classes ferm'ees par mineurs).

Les classes de graphes `a� expansion born'ee sont une g'en'eralisation des classes propres ferm'ees par mineurs et des classes `a� degr'e born'e. Ces classes sont d'efinies `a� partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rank r, ∇<sub>r</sub>(G). Ces classes sont 'egalement caract'eris'ees par l'existence de colorations induisant des graphes de faible tree-width ou de faible tree-depth. Ces r'esultats am`a�ne diff'erents nouveaux algorithmes en temps lin'eaire, tel qu'un algorithme pour compter tous les sous-graphes isomorphes `a� un graphe fix'e, ou un algorithme testant l'existence d'un sous-ensemble de sommets de taille born'ee a priori tel que le sous-graphe induit satisfasse une propri'et'e arbitraire (mais fix'ee) exprim'ee en logique du premier ordre. Nous montrons 'egalement que pour tout p fix'e, le calcul de la distance entre deux points (jusqu'`a� une distance de p) peut `a�tre effectu'e en temps constant apr`a�s un pr'etraitement effectu'e en temps lin'eaire. Nous montrons 'egalement, 'etendant ainsi divers r'esultats pr'ec'edents, que les classes de graphe ayant une expansion sous-exponentielle ont des s'eparateurs de taille sous-lin'eaire. Ce r'esulat est optimal en g'en'eral.

Nous 'etudions les dualit'es restreintes d'homomorphismes dans le contexte des classes d'expansion born'ee. Ceci repr'esente une g'en'eralisation des dualit'es restreintes mises en 'evidence pr'ec'edemment pour les graphes de degr'e born'e et pour les classes propres ferm'ees par mineur. Ce r'esultat est li'e au “coloration de distance” des graphes et `a� une “approximation” de la conjecture de Hadwiger.

Nous carat'erisons les notions d'arrangeabilit'e et d'admissibilit'e en termes de ∇₁(G) (la conjecture de Burr – Erdős 'etant, elle, li'ee `a� ∇₀(G)). Nous en d'eduisons la lin'erit'e du nombre de Ramsey et du nombre chromatic de jeu pour de nouvelles classes de graphes.

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Les orientations régulières, i.e. les orientations telles que presque tous les sommets aient le même degré entrant, relient de nombreuses propriétés combinatoires et topologiques, telles que l'arboricité, le page number et la planarité. Ces orientations constituent un outil de base dans la résolution de problèmes combinatoires dans lesquels des propriétés topologiques doivent être conservées. L'augmentation de graphes planaires est un exemple simple de tels problèmes.

La traversée d'un courbe simple auto-sécante du plan ayant des points de multiplicité au plus deux définit une suite à double occurences. C.F. Gauss a émis la conjoncture que ces séquences pouvaient être caractérisées par leurs propriétés d'entrelacement. Cette conjecture a été prouvée par P. Rosenstiehl en 1976. Nous donnons ici une preuve simple et auto-suffisante de cette caractérisation. Cette nouvelle preuve repose sur l'opération de “D-switch”.

Nous montrons qu'un complexe simplicial abstrait S peut être réalisé géométriquement dans l'espace Euclidien de dimension (d-1), o`a� d=P(S) est la dimension de Dushnik-Miller de l'ordre partiel d'inclusion des faces de S.

Nous définissons le genre réduit d'un multigraphe comme étant le genre minimum d'un hypergraphe possédant les mêmes adjacences avec les mêmes multiplicités. Par une étude des hypergraphes plongés, nous obtenons de nouvelles bornes sur le nombre chromatique, le nombre de clique et l'arboricité des graphes simples de genre réduit donné. Nous présentons de nouveaux problèmes dérivés concernant la coloration et la représentation des graphes.

Le tracé de structures combinatoires constitue un nouveau défi visant un meilleur contr`a�le des données, aussi bien dans l'industrie que dans les affaires. En parlant de graphes, on entend généralement la notion de carte, le système de rotation des arêtes autour des sommets étant généralement spécifié par les structures de données. Le parcours constitue une étape cruciale des algorithmes de tracé. Le parcours en profondeur (DFS) a engendré dans le passé des algorithmes bien connus de test de planarité, de transformation de cartes et de tracé de graphe. Le parcours en largeur (BFS) qui a, par contre, été relativement négligé, apparaît comme l'outil approprié du codage des cartes. Nous explicitons ici une bijection entre les cartes pointées ayant m arêtes et les involutions connexes de {0,1,...,2m+1}.

Nous présentons un algorithme simple en temps linéaire de recherche d'une configuration de Kuratowski dans un graphe DFS coarbre-critique. Par soucis de clarté, les preuves des théorèmes utilisés sont esquissés. L'algortihme présenté constitue la deuxième moitié de l'algorithme de recherche en temps linéaire d'une configuration de Kuratowski dans un graphe non planaire mis en œuvre dans PIGALE (“Public Implementation of a Graph Algorithm Library and Editor”, librement accessible à l'adresse http://pigale.sourceforge.org).

Les Topic Maps ont été introduites afin de permettre l'échange et la représentation d'informations relatives à la structure des ressources informationelles définies par des entité et des relations entres les entités. Les graphes et les hypergraphes ont été intdroduits en mathématiques discrètes pour des raisons similaires. Les besoins industriels liés aux Topic Maps concernent non seulement leur codage par une structure de données, mais aussi les requêtes complexes dont ils peuvent être l'objet, telles que parcours, analyse de structure, recherche de coupes minimales, etc. Le pardigme qui semble adaptés à ces problématiques semble reposé sur la strcture d'hypercarte introduite il y a quelques dizaines d'années. Cet article présente cet objet combinatoire, les structures de données associées et des considérations algorithmiques liées. Nous montrons que la théorie topologique des graphes constitue l'outil mathématique et algorithmique adapté à un traitement performant des Topic Maps.

Les Topic Maps ont été développés afin de représenter des structures de mise en relations de sujets indépendamment des ressources les documentant, et afin de permettre une représentation standard et une interopérabilité de ces structures. La spécification ISO 13250 XTM a fournit une représentation syntaxique robuste dans le cadre XML, permettant le traitement et l'échange de Topic Maps. Néanmoins, les Topic Maps ont souffert de l'absence d'une véritable description formelle et d'un modèle conceptuel. Nous proposons un tel modèle, basé sur la notion d'hypergraphe et de connexité. Ce modèle aborde le problème critique de l'organisation des Topic Maps en niveaux sémantiques, et fournit une procédure de vérification de la consistance sémantique d'une Topic Map. Enfin, ce modèle semble suffisamment générique pour être utilisé comme fondation d'autres standards, tels que RDF.

Nous donnons une caractérisation des graphes DFS-coarbre critique qui est centrale à l'algorithme en temps linéaire de recherche d'une configuration de Kuratowski mis en œuvre dans PIGALE

Nous prouvons qu'un système de contact d'arcs de Jordan est rectifiable si, et seulement si, il est extensible en un système de pseudo lignes.

L'importance croissance de l''education `a� distance (“e-learning”) a 'et'e un acc'el'erateur `a� l''emergence de services d''education bas'es sur Internet. Dans cet `a�ge de l'information, des efforts importants et continus ont 'et'e apport'es au d'eveloppement de nouvelles technologies Web pour l''education, mettant en relation les ressources humaines et les attentes d''education. Cet article pr'esente les possibilit'es de Pliant en tant que logiciel adaptable facilitant le d'eveloppement de syst`a�mes de gestion d''education `a� distance en preservant les attentes en termes d''education et de g'enie logiciel. Il pr'esente les possibilit'es de Pliant en tant que nouvel outil logiciel et technologie Web d'edi'es l''education `a� distance.

Nous donnons une condition n�cessaire et suffisante pour qu'un graphe biparti connexe donn� soit le graphe d'incidence d'une famille de segments et de points. Nous d'eduisons que tout graphe 4-connexe 3-coloriable planaire est le graphe de contact d'une famille de segments et que tout graphe planaire 4-colori'e sans C₄ induit utilisant 4 couleurs est le graphe d'intersection d'une famille de segments.

Les classes d'expansion bornées généralisent les classes propres fermés par mineurs et les classes de degré borné. Pour tout classe C d'expansion bornée et pour tout entier p, il existe une constante N(C,p) telle que l'enesemble des sommets de tout graphe G∈C puisse être partionné en N(C,p) parties, i≤p quelconques d'entre elles induisant un sous-graphe de tree-width au plus (i-1) (en fait, de tree-depth au plus i, ce qui est sensiblement plus fort). De telles partitions sont centrales pour la résolution de certains problèmes liés à l'existence d'homomorphismes tels que les dualités restreintes d'homomorphismes. Nous explicitons un algorithme simple calculant de telles partitions et prouvons que si les graphes d'entrée sont restreints à une classe quelconque C d'expansion bornée, le temps d'exécution de l'algorithme est borné par une fonction linéaire de l'ordre du graphe (pour C et p fixés). De ce résultat, nous déduisons un algorithme en temps linéaire pour la recherche d'un sous-graphe isomorphe à un motif fixé au seins de graphes appartenant à une classe fixé d'expansion bornée. Plus généralement, si φ est un expression du premier ordre, la propriété `∃X: (|X|≤p) ∧(G[X]⊧φ)” peut être décidé en temps linéaire pour des graphes d'entrée restreints à une classe fixée d'expansion bornée.

Nous introduisons les classes de graphes d'ém expansion bornée comme généralisation des classes propres fermées par mineurs et des classes de degré borné. La définition de ces classes est basée sur un nouvel invariant, le greatest reduced average density (grad) de G de r, ∇_r(G). Nous généralisons à ces classes des résultats prouvés pour les classes propres fermées par mineur et les classes de degré borné, tels que l'existence de partitions de faible largeur d'arbre, l'existence d'un algorithme en temps linéaire testant l'existence de sous-graphes isomorphes à un motif fixé, et l'existence de dualités restreintes d'homomorphismes.

De nombreux th'eor`a�mes de repr'esentation s''etendent des graphes planaires aux hypergraphes planaires. N'eanmoins, bien que la d'emonstration de la repr'esentabilit'e des graphes planaires par un syst`a�me de contacts de triangles conduise `a� un algorithme simple en temps lin'eaire, l'extension aux hypergraphes lin'eaires planaires ne semble pas avoir de d'emonstration simple. Nous en donnons une d'emonstration ici, qui repose sur la caract'erisation des hypergraphes de contact d'une famille de segments.

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

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

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

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

Un graphe biparti planaire G étant donné, nous assignons à ses sommets des segments horizontaux et verticaux, de telle sorte que (a) deux segments n'aient jamais de point interieur commun, (b) deux segments aient un point commun si et seulement si les sommets correspondants sont adjacents dans G.

Nous prouvons que tout graphe plan peut être représenté par un système de triangles en contact, i.e. par une collection de disques triangulaires disjoints sauf en leur points de contact, tout point de contact étant le sommet d'exactement un triangle. Nous en déduisons des représentations par contacts d'objets en forme de T et de Y, respectivement. De plus, nous montrons que les représentations par contacts de triangles d'un graphe maximal planaire sont en bijection avec les décompositions de Schnyder du graphe en trois arbres.

Une famille d'arcs de Jordan telle que deux arcs ne soient nulle part tangents definit un hypergraphe dont les sommets sont les arcs et dont les arêtes sont les points d'intersection. Nous dirons que l'hypergraphe a une représentation forte par intersection et, si chaque point d'intersection est intérieur à au plus un arc, nous dirons que l'hypergraphe a une représentation forte par contact. Nous caractérisons tout d'abord les hypergraphes ayant une représentation forte par contact et en déduisons des conditions suffisantes pour qu'un graphe simple planaire ait une représentation forte par intersection. Ensuite, à l'aide du théorème des quatres couleurs, nous prouvons qu'une large classe de graphes simples planaires ont une représentation forte par intersection.

Nous relions le nombre chromatique acyclique et “étoilé” d'un graphe au nombre chromatique de ses mineurs. En conséquence, nous montrons que l'ensemble des graphes planaires sans triangles est borné par la relation d'homomorphisme par un graphe sans triangle. Nous améliorons également, pour les graphes planaires, la meilleure borne connue sur le nombre chromatique étoilé de 80 à 30. Notre méthode se généralise à toutes les classes fermées par mineur et offre une nouvelle vision de la conjecture de Hadwiger.

Nous montrons que l'ensemble des sommets d'un multigraphe G sans jumeaux a un plongement sur un ensemble de points P d'un espace Euclidien R^k, tel que le groupe d'automorphismes de G soit isomorphe au groupe d'isom�tries de R^k pr�servant gloablement P.

Nous montrons que les cartes point'ees `a m arêtes sont en bijection avec les mots à double occurrences standards à (m+1) symbols.

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

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

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

PICTEL est un logiciel de trac'e automatique de sch'ema 'el'ectriques d'avions int'egr'e au logiciel CATIA

Penelope est un logiciel de conception et de simulation de tissu cha`a�nes et trames

Ce programme est un logiciel de trac'e automatique de diagrammes hierarchiques 4-faces

Le projet Pliant consiste en la cr'eation, sous licence GPL, d'un ensemble, coh'erent et minimal, contenant les outils de base n'ecessaires `a� la plupart des utilisateurs, outils concentr'es dans un code source de faible taille `a� l'aide d'un nouveau langage permettant de focaliser l''ecriture sur ce qui est pertinent, sans emp`a�cher le programmeur d'intervenir `a� n'importe lequel des niveaux d'abstraction, d'imposer n'importe quelle exception aux r`a�gles g'en'erales. Le projet Pliant est accessible `a� http://fullpliant.org.

Pigale intègre une librairie d'algorithmes de traitements de graphe écrite en langage C++ et un éditeur de graphe basé sur les librairies Qt et OpenGL. Ce programme est particulièrement destiné à la recherche théorique sur les graphes topologiques. Pigale est disponible sous licence GPL et peut être téléchargé par FTP ou CVS depuis l'adresse: http://sourceforge.net/projects/pigale/

Ariane est une logiciel de gestion bibliographique

Le sujet de cette thèse est le concept d'orientation bipolaire d'un graphe 2-connexe, i.e. d'orientation acyclique possédant une seule source et un seul puits. L'étude débute par l'abstraction des orientations bipolaires dans le cadre des matroïdes orientés réguliers; une telle abstraction est particulièrement appropriée à l'étude des propriétés d'effacement, de contraction et d' extension. Le codage original d'une orientation bipolaire quelconque par un graphe parfait conduit à une nouvelle caractérisation des matroïdes graphiques. La planarité d'un graphe est alors caractérisée en terme de dimension de l'ordre partiel d'arêtes induit par une orientation bipolaire. Dans le cas graphique, il est établi que deux orientations bipolaires quelconques d'un graphe 3-connexe sont connectées par une séquence d'orientations bipolaires obtenues à chaque étape en inversant l'orientation d'exactement une arête. Il est montré que dans le cas des graphes planaires, l'ensemble des orientations bipolaires est organisé en treillis distributif. La même structure est également mise en évidence sur l'ensemble des décompositions d'un graphe maximal planaire en trois arbres de Schnyder. Dans le dernier chapitre sont prouvés deux théorèmes de représentation: tout graphe planaire peut être représenté par une famille de triangles en contact; tout graphe biparti planaire peut être représenté par une famille de segments horizontaux et verticaux en contact.

L'orientation des langages de programmation semblent suivre deux orientations principales. La première correspond à la tentative des grandes compagnies d'acquérir de plus en plus d'emprise sur les utilisateurs finaux, tout en limitant leur propre responsabilité dans une sorte de “démocratie” sous tutelle. La seconde est une quête d'indépendance des utilisateurs qui s'exprime, notamment, au sein du mouvement “logiciel libre”. Alors que la première tendance mène à une sévère limitation des possibilités offertes aux programmeurs et à une uniformisation des logiciels “personnels” restreints à des “macros-logiciels”, le besoin qu'a la seconde d'une cohérence interne pourrait amener à introduire un nouveau type de système d'exploitation responsable d'une compilation indépendante du langage, que nous appelons système d'exploitation de langages, permettant un nouveau type d'intégration: l'intégration au niveau du langage.