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 . [1] 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.
A Kuratowski subgraph of a nonplanar graph can be found in linear time, as measured by the size of the input graph. [2] This allows the correctness of a planarity testing algorithm to be verified for nonplanar inputs, as it is straightforward to test whether a given subgraph is or is not a Kuratowski subgraph. [3] Usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e.g., in branch and cut algorithms for crossing minimization. It is possible to extract a large number of Kuratowski subgraphs in time dependent on their total size. [4]
Kazimierz Kuratowski published his theorem in 1930. [5] The theorem was independently proved by Orrin Frink and Paul Smith, also in 1930, [6] but their proof was never published. The special case of cubic planar graphs (for which the only minimal forbidden subgraph is ) was also independently proved by Karl Menger in 1930. [7] Since then, several new proofs of the theorem have been discovered. [8]
In the Soviet Union, Kuratowski's theorem was known as either the Pontryagin–Kuratowski theorem or the Kuratowski–Pontryagin theorem, [9] as the theorem was reportedly proved independently by Lev Pontryagin around 1927. [10] However, as Pontryagin never published his proof, this usage has not spread to other places. [11]
A closely related result, Wagner's theorem, characterizes the planar graphs by their minors in terms of the same two forbidden graphs and . Every Kuratowski subgraph is a special case of a minor of the same type, and while the reverse is not true, it is not difficult to find a Kuratowski subgraph (of one type or the other) from one of these two forbidden minors; therefore, these two theorems are equivalent. [12]
An extension is the Robertson–Seymour theorem.
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.
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 nor K3,3. 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.
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.
In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.
Klaus Wagner was a German mathematician known for his contributions to graph theory.
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.
In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof was announced in 2016, and published in four papers in 2020.
