A graph that can be
regularly imbedded
in the plane (cf.
Graph imbedding).
In other words, a graph
is said to be
planar
if it can be represented in the plane so that various points of
the plane correspond to its vertices and so that the lines corresponding
to the edges of the graph do not pass through
the points which correspond to the vertices (except for their
terminal points) and do not mutually intersect. Problems
such as the problem of colouring maps, the
problem of design of communications, problems in
radio-electronics which involve the realization of a circuit
with the aid of planar printed subcircuits, etc., can be
reduced to the study of planar graphs. Any
regular (with non-intersecting edges) imbedding of a connected planar
graph involves a subdivision of the plane into
individual domains (faces). Such a subdivision of the plane is known as a
planar map.
Euler's formula
where
is the number of vertices,
is the number of edges and
is the number of faces of the map (including the exterior
face) applies to any planar map. It follows that the graph
(the complete graph with
)
and
(the complete bipartite graph, cf. also
Graph, bipartite)
which has three vertices in each of its parts, are not planar
(
Fig. a).
Figure: g044990a
In a certain sense, these graphs are minimal non-planar graphs, according to the
Pontryagin–Kuratowski theorem:
A graph is planar if and only if it does not contain a subgraph homeomorphic to the graph
or
(cf.
Graph homeomorphism).
There also exist other criteria of planarity (i.e. of whether
or not a graph is planar). In particular, a graph
is planar if and only if each of
its non-trivial doubly-connected components has a cycle basis
and an additional cycle
such that any edge of
is part of precisely two out of these
cycles (a
cycle basis
is a subset of cycles of a given graph which is independent
and complete in the set of all cycles of the
graph with respect to the operation of addition modulo 2, cf.
Graph).
Any planar graph can be represented in the plane so that
all its edges are segments of a straight line. Any triply-connected graph (cf.
Graph, connectivity of a)
can be uniquely imbedded in the sphere (up to a
homeomorphism of the sphere). Each imbedding of a planar graph
in the plane, and hence each planar map,
can be brought into one-to-one correspondence with its geometric
dual graph,
which is obtained as follows. A vertex of the planar graph is
introduced into each face of the map and, if two faces have a common edge
,
the vertices they contain are joined by the edge
which intersects
only once (in
Fig. bthe imbedding of the graph is represented
by continuous lines, while the dotted lines represent its dual graph).
Figure: g044990b
A planar map each side of which is bounded by three edges is said to be a
planar triangulation.
The number of edges of a planar triangulation with
vertices is
.
An intensively studied subject in the theory of
graphs is the colouring of planar graphs (cf.
Graph colouring);
for non-planar graphs one studies various numerical characteristics yielding
the degree of non-planarity, including the genus, the thickness
or coarseness of the graph, the number of crossings, etc. (cf.
Graph imbedding).