Graphe planaire extérieurvignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
Graph embeddingIn topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Graphe de blocsvignette|upright=1.4|Un graphe de blocs. En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique. Les graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi), mais ce nom fait plus référence aux graphes cactus, qui sont des graphes dans lesquels chaque composante biconnexe non triviale est un cycle.
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.
Graphe de WagnerLe graphe de Wagner est, en théorie des graphes, un graphe 3-régulier possédant 8 sommets et 12 arêtes. C'est un cas particulier d'échelle de Möbius. Le graphe de Wagner est un cubique et hamiltonien, il peut être défini par la notation LCF [4]8. Une autre façon de le construire est de le considérer comme une échelle de Möbius, c'est-à-dire un graphe échelle sur le ruban de Möbius. Le diamètre du graphe de Wagner, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 4.
Graphe trivialement parfaitvignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Graphe diamantLe graphe diamant est, en théorie des graphes, un graphe possédant 4 sommets et 5 arêtes. Il peut être construit à partir du graphe complet à quatre sommets, K4 en lui retirant une arête quelconque. Il est hamiltonien, une autre façon de le construire étant de partir du graphe cycle C4 et de lui ajouter une arête quelconque. Le nom de graphe diamant est employé au sein de la classification de l'ISGCI (Information System on Graph Classes and their Inclusions).
Graphe parfaitEn théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
Kuratowski's theoremIn graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on five vertices) or of (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).
Homéomorphisme de graphesEn théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes. Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie. Subdivision La subdivision d'une arête conduit à un graphe contenant un nouveau sommet et où l'on a remplacé l'arête par deux nouvelles arêtes, et .
