Kuratowski's theorem
The Kuratowski's theorem (after Kazimierz Kuratowski ) is a set of the graph theory , the important statements on planar graphs makes and the question of the planarity (planarity) of a graph answered.
Planarity
In general terms, a graph is planar (flattenable) if and only if it is possible to draw the graph in the plane in such a way that the edges of the graph do not intersect. The edges may only touch in the nodes of the graph.
The following two graphs are planar, the planarity of only becoming apparent when you draw differently.
The graphs K 5 and K 3,3
Kuratowski's theorem uses two special graphs: and . When it is the complete graph with 5 nodes (see Fig. 2), in a completely bipartite graph , which is divided into two each three-element subsets (see Fig. 3). Both graphs are not planar. They are actually the smallest non-planar graphs around, which follows directly from Kuratowski's theorem.
Kuratowski's theorem
Kuratowski's theorem says that a graph is planar if and only if it does not have a subgraph that is a subdivision graph of the or the . A subdivision graph is obtained by repeatedly replacing an edge with an incident pair of edges. Alternatively, one can formulate that a graph is planar if and only if it contains neither the nor that as a minor .
See also
literature
- Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages, online version ).
- Kazimierz Kuratowski : Sur leproblemème des courbes gauches en topologie . In: Fund. Math. . 15, 1930, pp. 271-283.