
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
(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
(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
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
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
. 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
or
.
Kuratowski subgraphs
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
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
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.
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
) 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
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.
[.]
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
References
{{reflist
Statements about planar graphs
Theorems in graph theory