Planar graph

from Wikipedia, the free encyclopedia
Planar drawing of the

In graph theory, a planar or flattenable graph is a graph that can be represented on a plane, with points for the nodes and lines for the edges , so that no edges intersect.

definition

A graph is called planar or flattenable if it is embedded in the plane ; that is, it can be drawn in the plane so that its edges are represented by Jordan curves which only intersect at common end points. The embedding (also drawing ) of the graph is a plane graph . According to Wagner and Fáry's theorem, there is also an embedding for every planar graph in which its edges are represented as segments.

The embedding divides the plane into contiguous areas or areas that are bounded by the edges of the graph. The bounding edges of an area form its border. The unconstrained area around the graph is called the outer area or outer area . Two embeddings are called equivalent if there is an isomorphic map between the boundaries of their domains.

Related terminology

Example of an extraplanar graph; planar embedding on the left, planar embedding on the right, in which all nodes lie on the outer area

A graph is called maximally planar or triangle graph if it is planar and no edge can be added to it without losing its planarity.

A graph is said to be almost planar or critically planar if the graph becomes planar by removing any node. Example: K 5 is almost planar.

A graph is called extra- planar (often also outer- planar or circular planar ) if it can be embedded in the plane in such a way that all of its nodes lie on the edge of the same area.

properties

  • Animation : The Petersen graph contains the completely bipartite graph as a
    minor and is therefore not planar.
    The Kuratowski's theorem is a non-geometric characterization of planar graphs. It says that a graph is planar if and only if it does not have a subgraph that is a subdivision graph of the complete graph or the fully bipartite graph . 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 .
  • From Euler's polyhedron theorem it follows that the number of areas of each embedding is the same.
  • For a planar graph without loops and multiple edges, the polyhedron substitute gives the estimate . For triangle-free graphs with at least 3 nodes, this can be improved to the following inequality:
  • If a planar graph is 3-fold connected , all of its embeddings (except for a global reorientation) are equivalent.
  • A planar graph with nodes is maximally planar if and only if it has edges.
  • A planar graph can be at most 5-times connected and there is always a node with node degree at most 5.
  • According to the Koebe-Andreev-Thurston theorem, for every planar graph there is an associated circle packing whose contact graph is isomorphic to the origin graph .

The planarity of a graph can be tested with various algorithms in linear runtime .

Euler's polyhedron substitute

The Euler Polyedersatz states that any finite contiguous planar graph with nodes , edges and surfaces of the following equation satisfied:

In a finite connected simple planar graph, each surface is bounded by at least three edges, and each edge touches at most two surfaces. With the polyhedron theorem one can show that the following applies to these graphs:

The polyhedron substitute also applies to convex polyhedra . This is no coincidence: any convex polyhedron can be transformed into a coherent simple planar graph using the Schlegel diagram of the polyhedron, a central projection of the polyhedron onto a plane whose projection center is near the center of one of the polyhedra's faces . Not every planar graph corresponds to a convex polyhedron in this way: The trees, for example, do not.

The set of Steinitz says that of convex polyhedra formed graph exactly the finite 3-contiguous are simple planar graph. In general, the polyhedron substitute applies to any polyhedron whose faces are simple polygons that, regardless of their convexity, form a surface that is topologically equivalent to a sphere .

Average degree of knot

Related planar graph with more than one edge satisfy the inequality , because each surface adjacent to at least three edges and each edge bounded exactly two surfaces. From the inequality it follows for the average degree of knot

This means that for finite planar graphs the average nodal degree is less than 6. Graphs with a higher average nodal degree cannot be planar.

Planar graph density

The density of a planar graph or network is defined as a ratio of the number of edges to the number of maximum possible edges in a network with nodes , given by a planar graph with :

A connected planar graph with a minimal number of edges , i.e. a tree , has one edge less than nodes, i.e. is and . For a connected planar graph with a maximum number of edges .

Combinatorics

The number of simple planar graphs without numbered nodes increases faster than exponentially with the number of nodes . The following table shows the numbers determined with the help of a computer for :

Number of planar graphs without numbered nodes
n all coherent
1 1 1
2 2 1
3 4th 2
4th 11 6th
5 33 20th
6th 142 99
7th 822 646
8th 6966 5974
9 79853 71885
10 1140916 1052805
11 18681008 17449299
12 333312451 313372298

Dual graphs

The red graphs are each dual to the blue graphs, which are isomorphic to one another, but are not themselves isomorphic to one another. The blue graphs are different embeddings of isomorphic graphs.
Dodecahedron graph with dual icosahedron graph

Every planar graph has a dual graph . This is a graph where each area of ​​the graph is assigned a node that lies within that area and vice versa, and each edge is assigned an edge that separates the two areas that are assigned to the end nodes of the edge of the original graph, and connects the two nodes associated with the neighboring faces of the edge of the original graph. The dual edges intersect the original edges. In the figures, the original graphs are colored blue and the dual graphs are colored red.

If the graph is not only planar but also connected , then the number of nodes of the dual graph corresponds to the number of surfaces of the original graph and vice versa, and the number of edges remains constant. In the connected case there are bijective mappings between the sets of edges of the two graphs and the sets of nodes and the set of surfaces.

The term dual is used because the property of being a dual graph is mutual, which means that a dual graph of is when a dual graph is of a connected graph . There can generally be several dual graphs for planar graphs, depending on the choice of planar embedding of the graph.

use

The study of the planarity of graphs is one of the classic subject areas of graph theory and is also often used as a strong prerequisite for propositions. The four-color theorem says that planar graphs can be colored with 4 colors . Triangle-free planar graphs are 3-colorable .

literature

Individual evidence

  1. sequence A033995 in OEIS
  2. Follow A003094 in OEIS
  3. ^ LR Foulds: Graph Theory Applications . In: Springer . 2012, pp. 66-67.