Kuratowski's theorem

In 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). A planar graph is a graph whose vertices can be represented by points in the Euclidean plane, and whose edges can be represented by simple curves in the same plane connecting the points representing their endpoints, such that no two curves intersect except at a common endpoint. Planar graphs are often drawn with straight line segments representing their edges, but by Fáry's theorem this makes no difference to their graph-theoretic characterization. A subdivision of a graph is a graph formed by subdividing its edges into paths of one or more edges. Kuratowski's theorem states that a finite graph is planar if it is not possible to subdivide the edges of or , and then possibly add additional edges and vertices, to form a graph isomorphic to . Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to or . If is a graph that contains a subgraph that is a subdivision of or , then is known as a Kuratowski subgraph of . With this notation, Kuratowski's theorem can be expressed succinctly: a graph is planar if and only if it does not have a Kuratowski subgraph. The two graphs and are nonplanar, as may be shown either by a case analysis or an argument involving Euler's formula. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph has a planar drawing, the paths of the subdivision form curves that may be used to represent the edges of itself. Therefore, a graph that contains a Kuratowski subgraph cannot be planar. The more difficult direction in proving Kuratowski's theorem is to show that, if a graph is nonplanar, it must contain a Kuratowski subgraph.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (12)

Personnes associées (2)

Unités associées (1)

Concepts associés (15)

Cours associés (2)

Séances de cours associées (17)

Atomic subgraphs and the statistical mechanics of networks

Sofia Charlotta Olhede

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...

2021

Simple Realizability of Complete Abstract Topological Graphs Simplified

Jan Kyncl

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

SPRINGER2020

Graph Learning with Partial Observations: Role of Degree Concentration

Ali H. Sayed, Augusto José Rabelo Almeida Santos

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections ...

IEEE2019

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Wagner's theorem

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

Mineur (théorie des graphes)

La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

Systèmes de contrôle en réseau : taux de convergence et diagrammes ME-427: Networked control systems

Explore le taux de convergence dans les systèmes de contrôle en réseau et le consensus dans les digrammes, en mettant l'accent sur les défis du calcul Pess (A) et de l'attribution de poids.

Graphiques et sous-graphes

Couvre les graphes mous et les sous-graphes induits en théorie des graphes.

Introduction à la théorie des graphiques MATH-261: Discrete optimization

Couvre les bases de la théorie des graphiques, y compris les flux de réseau, les degrés de sommets, les promenades et les sous-graphes.