Tree-depthIn graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.
Densité d'un grapheEn mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
Famille de Petersenthumb|300px|La famille de Petersen. Le graphe complet K6 est en haut de l'illustration, et le graphe de Petersen est en bas. Les liaisons bleues indiquent des transformations Δ-Y ou Y-Δ entre les graphe s de la famille. En mathématiques, et plus précisément en théorie des graphes, la famille de Petersen est un ensemble de sept graphes non orientés contenant le graphe de Petersen et le graphe complet K6. Cette famille a été découverte et étudiée par le mathématicien danois Julius Petersen.
Échelle de MöbiusDans la théorie des graphes, une branche des mathématiques, l'échelle de Möbius est un graphe cubique formé à partir du graphe cycle à sommets en ajoutant des arêtes entre les sommets opposés du cycle. Les graphes de cette famille sont nommés ainsi car, si l'on excepte , possède exactement cycles à 4 sommets qui, mis ensemble par leurs sommets partagés, forment l'équivalent d'un ruban de Möbius. Les échelles de Möbius ont été nommées et étudiées pour la première fois par Richard Guy et Frank Harary en 1967.
Peripheral cycleIn graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
Klaus WagnerKlaus Wagner (né le et mort le ) est un mathématicien allemand, connu dans son pays pour son rôle de pionnier de la théorie des graphes. Wagner étudia la topologie à l'université de Cologne sous la supervision de , lui-même ancien étudiant d'Issai Schur. Il reçut son doctorat en 1937 et enseigna à Cologne pendant de nombreuses années. En 1970, il choisit ce qui est aujourd'hui l'université de Duisbourg et Essen et il y resta jusqu'à sa retraite en 1978. Une festschrift fut publiée en son honneur en 1990.
Théorème du séparateur planaireEn théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets. Une forme plus faible du théorème séparateur avec un séparateur de taille au lieu de a été prouvée à l'origine par Ungar (1951), et la forme avec la borne asymptotique plus fine sur la taille du séparateur a été prouvée pour la première fois par Lipton & Tarjan (1979).
Contraction d'arêteEn théorie des graphes, une contraction d'arête est une opération sur un graphe. Elle consiste, de façon imagée, à contracter une arête d'un graphe, ce qui revient à fusionner ses deux extrémités. Cette opération est fondamentale pour la théorie des mineurs de graphe et elle est utilisée dans certains algorithmes et certaines preuves. Soit un graphe G=(V,E), contenant une arête (u,v), avec u différent de v.
Branch-decompositionIn graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.
Linkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
