Planar graph

A planar or planar graph is a graph in graph theory, which 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 planar if it has an embedding in the plane; ie it can be drawn in the plane so that its edges are represented by Jordan curves which intersect only at common endpoints. The embedding (also drawing ) of the graph is a plane graph. By the theorem of Fary also exists an embedding in which its edges are represented as ( straight-line ) distances for every planar graph.

By embedding the layer is in contiguous areas (including areas) divided, which are bounded by the edges of the graph. The bounding edges of a region form its edge. The unrestricted area around the graph around is called the outer region or outer surface. Two embeddings are called equivalent if there is an isomorphism between the edges of their territories.

Related Tendings

A graph is called maximal planar graph or triangle if it is planar and it is no edge can be added without loss of planarity is lost.

A graph is called planar or nearly critical planar if the graph is planar by the removal of any node. Example: K5 is almost planar.

A graph is called außerplanar (often außenplanar or circularly planar) if it can be so embedded in the plane such that all its vertices lie on one and the same territory edge.

Properties

• The set of Kuratowski 's a non- geometric characterization of planar graphs and allows to answer the question of the planarity of graphs.
• From the Eulerian Polyedersatz follows that the field number of each embedding is the same.
• For a planar graph without loops and multiple edges resulting from the Polyedersatz the assessment. This can be improved for triangle- free graph with at least 3 nodes yet on the following inequality:
• If a planar graph 3-fold -connected, so are all its embeddings (up to a global reorientation ) equivalent.
• A planar graph with vertices is maximal planar if it has edges.
• A planar graph can be up to 5-fold contiguous and there is always a node with node degree at most 5

The planarity of a graph can be tested using different algorithms in linear time.

Use

The investigation of the planarity of graphs is one of the classical topics of graph theory and is also often used as a strong requirement for phrases. So says the four- color theorem, that can be planar graphs with 4 colors dye. Triangle -free planar graphs are 3- colorable.