# Planar graph

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

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

- 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

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

- Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages, online version ).
- Lutz Volkmann:
*Fundamente der Graphentheorie*, Springer (Vienna) 1996, ISBN 3-211-82774-9 ( newer, online version "Graphs on all corners and edges" ; PDF; 3.7 MB)