Plane graph
A plane graph is a concrete representation of a graph as a subset of and thus a special case of a Euclidean graph for .
definition
A tuple (where the elements are called corners and the elements are edges) is called a planar graph if:
- consists of pairwise disjoint points of the .
- Each edge is a simple Jordan curve that connects two corners.
- The edges never intersect and only touch in the corners.
The following fourth condition is sometimes also stated in the literature:
- Different corners are connected by different edges.
This tightening is often required if one only wants to examine simple graphs for planarity . The above three points still allow multigraphs as an object under consideration.
A plane graph is called maximally plane if it is plane, but is no longer plane after adding any edge.
Differentiation from planar graphs
With planar graphs there is often a risk of confusion with planar graphs : Planarity is a property of abstract graphs , i.e. graphs, understood as a set of nodes and, depending on the definition, a different set of edges. However, a plane graph is a representation of an abstract graph as a subset of the . That's just how it is in the picture above . If you consider it as a subset of the , it must first be drawn differently in order to obtain a flat graph. The underlying abstract graph is planar regardless of how it is drawn in the specific case. By definition, planar graphs are precisely those graphs that are isomorphic to a planar graph.
properties
- For connected plane graphs, according to Euler's polyhedron theorem :
, where , and is the number of areas of the graph (including the outer area)
- Every maximally planar graph is maximally planar
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)