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 . ${\ displaystyle \ mathbb {R} ^ {2}}$ ${\ displaystyle q = 2}$

definition

A tuple (where the elements are called corners and the elements are edges) is called a planar graph if: ${\ displaystyle (V, E)}$ ${\ displaystyle V}$ ${\ displaystyle E}$

${\ displaystyle V}$ consists of pairwise disjoint points of the . ${\ displaystyle \ mathbb {R} ^ {2}}$
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

Example graphs G1 and G2

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. ${\ displaystyle \ mathbb {R} ^ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle \ mathbb {R} ^ {2}}$ ${\ displaystyle G_ {2}}$

properties

For connected plane graphs, according to Euler's polyhedron theorem :

${\ displaystyle n-m + f = 2}$ , where , and is the number of areas of the graph (including the outer area) ${\ displaystyle n = | V |}$ ${\ displaystyle m = | E |}$ ${\ displaystyle f}$

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)