In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, Kuratowski's theorem is a mathematical
forbidden graph characterization
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 forbidde ...
of
planar graphs, 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.
Biography and studies
Kazimierz Kuratowski was born in Warsaw, (t ...
. 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
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 ...
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 i ...
on six vertices, three of which connect to each of the other three, also known as the
utility graph
As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...
).
Statement
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
In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straigh ...
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
.
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 fo ...
. 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, as measured by the size of the input graph. This allows the correctness of a
planarity testing
In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer sc ...
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 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.
Biography and studies
Kazimierz Kuratowski was born in Warsaw, (t ...
published his theorem in 1930. The theorem was independently proved by
Orrin Frink
Orrin Frink Jr. (31 May 1901 – 4 March 1988). was an American mathematician who introduced Frink ideals in 1954.
Frink earned a doctorate from Columbia University in 1926 or 1927 and worked on the faculty of Pennsylvania State University for 41 ...
and
Paul Smith, also in 1930, 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
Karl Menger (January 13, 1902 – October 5, 1985) was an Austrian-American mathematician, the son of the economist Carl Menger. In mathematics, Menger studied the theory of algebras and the dimension theory of low- regularity ("rough") curves ...
in 1930.
Since then, several new proofs of the theorem have been discovered.
In the
Soviet Union
The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a List of former transcontinental countries#Since 1700, transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, ...
, 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 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.
See also
*
Kelmans–Seymour conjecture
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 . It is named for Paul Seymour and Alexander Kelmans, who independently descri ...
, that 5-connected nonplanar graphs contain a subdivision of
References
{{reflist
Planar graphs
Theorems in graph theory