HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, Kuratowski's theorem is a mathematical
forbidden graph characterization In graph theory, a branch of mathematics, many important families of Graph (discrete mathematics), 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 whic ...
of
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, named after
Kazimierz Kuratowski Kazimierz Kuratowski (; 2 February 1896 – 18 June 1980) was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Ma ...
. It states that a finite graph is planar if and only if it does not contain a subgraph that is a
subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rush ...
of K_5 (the
complete graph 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 i ...
on five vertices) or of K_ (a
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...
on six vertices, three of which connect to each of the other three, also known as the utility graph).


Statement

A
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
is a graph whose vertices can be represented by points in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
, 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 segment In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
s representing their edges, but by
Fáry's theorem In the mathematical field of graph theory, Fáry's theorem states that any simple graph, simple, planar graph can be Graph drawing, drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as ...
this makes no difference to their graph-theoretic characterization. A
subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rush ...
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 G is planar if it is not possible to subdivide the edges of K_5 or K_, and then possibly add additional edges and vertices, to form a graph
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to G. Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is
homeomorphic In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
to K_5 or K_.


Kuratowski subgraphs

If G is a graph that contains a subgraph H that is a subdivision of K_5 or K_, then H is known as a Kuratowski subgraph of G. 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 K_5 and K_ are nonplanar, as may be shown either by a case analysis or an argument involving
Euler's formula Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the fundamental relationship between the trigonometric functions and the complex exponential function. Euler's formula states that, for ...
. Additionally, subdividing a graph cannot turn a nonplanar graph into a planar graph: if a subdivision of a graph G has a planar drawing, the paths of the subdivision form curves that may be used to represent the edges of G 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.


Algorithmic implications

A Kuratowski subgraph of a nonplanar graph can be found in
linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
, as measured by the size of the input graph. 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. Usually, non-planar graphs contain a large number of Kuratowski-subgraphs. The extraction of these subgraphs is needed, e.g., in
branch and cut Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branc ...
algorithms for crossing minimization. It is possible to extract a large number of Kuratowski subgraphs in time dependent on their total size.


History

Kazimierz Kuratowski Kazimierz Kuratowski (; 2 February 1896 – 18 June 1980) was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Ma ...
published his theorem in 1930. The theorem was independently proved by Orrin Frink and Paul Smith, also in 1930, but their proof was never published. The special case of
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
planar graphs (for which the only minimal forbidden subgraph is K_) was also independently proved by
Karl Menger Karl Menger (; January 13, 1902 – October 5, 1985) was an Austrian-born American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebra over a field, algebras and the dimension theory of low-r ...
in 1930. Since then, several new proofs of the theorem have been discovered. In the
Soviet Union The Union of Soviet Socialist Republics. (USSR), commonly known as the Soviet Union, was a List of former transcontinental countries#Since 1700, transcontinental country that spanned much of Eurasia from 1922 until Dissolution of the Soviet ...
, Kuratowski's theorem was known as either the Pontryagin–Kuratowski theorem or the Kuratowski–Pontryagin theorem, as the theorem was reportedly proved independently by
Lev Pontryagin Lev Semyonovich Pontryagin (, also written Pontriagin or Pontrjagin, first name sometimes anglicized as Leon) (3 September 1908 – 3 May 1988) was a Soviet mathematician. Completely blind from the age of 14, he made major discoveries in a numbe ...
around 1927. However, as Pontryagin never published his proof, this usage has not spread to other places.


Related results

A closely related result, Wagner's theorem, characterizes the planar graphs by their minors in terms of the same two forbidden graphs K_5 and K_. 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.. An extension is the
Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is ...
.


See also

* Kelmans–Seymour conjecture, that 5-connected nonplanar graphs contain a subdivision of K_5


References

{{reflist Statements about planar graphs Theorems in graph theory