You get a bonus - 1 coin for daily activity. Now you have 1 coin

Planar graph Pontryagin-Kuratovsky theorem

Lecture



A planar graph is a graph that can be drawn on a plane without intersecting edges. In other words, a graph is planar if it is isomorphic to some flat graph , that is, the graph depicted on the plane so that its vertices are points of the plane, and the edges are curves on it. The areas into which the graph breaks a plane are called its faces . The unrestricted part of the plane is also a face, the so-called outer face .

Content

  • 1 The simplest properties of flat graphs
    • 1.1 Euler Formula
  • 2 Two examples of non-planar graphs.
    • 2.1 A complete graph with five vertices
    • 2.2 "Houses and wells"
  • 3 Theorem Pontryagin - Kuratovsky
  • 4 Computerized planarity check
  • 5 Signs of non-planar graphs
  • 6 Planar graphs in problems
  • 7 Generalizations
  • 8 See also
  • 9 Notes
  • 10 References

The simplest properties of flat graphs [edit]

Euler's formula [edit]

For a connected flat graph, the following relation between the number of vertices   Planar graph Pontryagin-Kuratovsky theorem ribs   Planar graph Pontryagin-Kuratovsky theorem and faces   Planar graph Pontryagin-Kuratovsky theorem (including outer edge):

  Planar graph Pontryagin-Kuratovsky theorem

It was found by Euler in 1736 [1] when studying the properties of convex polyhedra. This relationship holds true for other surfaces up to a coefficient called the Euler characteristic. This is an invariant of the surface, for a plane or sphere it is equal to two, and, for example, for a torus - zero.

The formula has many useful consequences. First, all flat layouts of one graph have the same number of faces. Secondly, if each face is bounded by at least three edges (provided that there are more than two edges in the graph), and each edge separates two faces , then

  Planar graph Pontryagin-Kuratovsky theorem

Consequently,

  Planar graph Pontryagin-Kuratovsky theorem

that is, with a larger number of edges, such a graph is obviously non-planar. The converse is not true: the Count Petersen can be taken as a counter-example. It follows that in the planar graph one can always find a vertex of degree at most 5.

The general formula is also easily generalized to the case of a disconnected graph:

  Planar graph Pontryagin-Kuratovsky theorem

Where   Planar graph Pontryagin-Kuratovsky theorem - the number of connected components in the graph.

Two examples of non-planar graphs [edit]

Full graph with five vertices [edit]

  Planar graph Pontryagin-Kuratovsky theorem
K 5 , full graph with 5 vertices

Lemma. A full graph with five vertices (K 5 ) cannot be laid on a plane.

Evidence. For it is not performed   Planar graph Pontryagin-Kuratovsky theorem .

"Houses and wells" [edit]

  Planar graph Pontryagin-Kuratovsky theorem
Count "houses and wells" (K 3,3 )

The problem of three wells . There are three houses and three wells. Is it possible to build paths between houses and wells in such a way that a path leads from each house to each well, and no two paths intersect. Bridges can not be built.

Lemma. A full bipartite graph with three vertices in each of the lobes (K 3,3 ) cannot be laid on a plane.

Evidence. According to the formula of Euler, the graph has 5 faces.

On the other hand: any face (including the outer one) contains at least 4 edges. Since each edge is included in exactly two faces, the ratio   Planar graph Pontryagin-Kuratovsky theorem , F is the number of faces, E is the number of edges. We substitute F = 5 and E = 9 into this inequality and see that it does not hold.

Pontryagin-Kuratovsky theorem [edit]

  Planar graph Pontryagin-Kuratovsky theorem
In general, finding K 5 or K 3,3 is quite difficult. Count Petersen is tightened in both K 5 and K 3.3 in some rather extraordinary ways.

The assertion is obvious: if a graph G contains a subgraph homeomorphic to K 5 or K 3,3 , then it cannot be expanded on a plane. It turns out the opposite is true.

A graph is planar if and only if it does not contain subgraphs that are homeomorphic to a complete graph of five vertices (K 5 ) or a graph of “houses and wells” (K 3,3 ).

The theorem can also be formulated in the following version (sometimes called the “Wagner theorem”).

A graph is planar if and only if it does not contain subgraphs that contract in K 5 or K 3,3 .

Computerized planarity check [edit]

The first algorithm, which finds the Kuratovsky subgraph for linear time, was developed in 1974 by Hopcroft and Tarjan. [2]

Signs of non-planar graphs [edit]

  • a sufficient condition - if the graph contains a bipartite subgraph K 3,3 or a complete subgraph K 5 , then it is non-planar;
  • necessary condition - if the graph is non-planar, then it must contain more than 4 vertices, the degree of which is more than 3, or more than 5 vertices of degree more than 2.

Planar graphs in problems [edit]

Coloring card . It is necessary to color a flat map with a given number of colors so that any two countries that have a common border area have different colors. It turns out that in the absence of enclaves, four colors are always enough, but this statement is extremely difficult to prove, see The problem of four colors.

Rectifying a graph (Fari theorem). Any flat graph can be redrawn so that it remains flat, and the edges become straight.

Generalizations [edit]

The graph fits on some surface if it can be drawn on it without intersecting the edges. The laid graph is called geometric , its vertices are points of the plane, and the edges are the lines on it. The areas into which the graph breaks the surface are called faces . Flat graph - a graph laid on a plane.

See also [edit]

  • Glossary of graph theory
  • Graph theory
  • Cell (graph theory)
  • Fari theorem
  • Gamma algorithm - algorithm for checking the planarity of the graph and its flat packing
created: 2015-01-07
updated: 2021-03-13
132734



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.