Can we draw graphs on a paper without edges crossing each other ? We can draw and so any graph on at most vertices can be drawn. What about ? First, we shall clarify what we mean by ’drawing’.
An embedding of the graph in the plane is a pair of functionf such that
is an injection.
, is a continuous simple path such that
for , we have that or equivalently
Since we are concerned with finite graphs, we shall assume that all ’s are polygonal line segments i.e., union of finitely many straight lines.
We shall never specify directly but more via drawings. A plane graph is a graph with its embedding . We shall view plane graphs as a subset of by identifying with . We shall denote by and by A graph isomorphic to a plane graph is called a planar graph. We refer to [Diestel 2000, Chapter 4] for various topological and geometric facts that shall be used in some of the proofs as well as more details. The most important of these is the Jordan curve theorem.
Let be a plane graph. is an open set and consists of finitely many connected components. Each connected component is called a face.
Here we list some properties of faces.
For any face and an edge , or . Thus we have that
If as a plane graph and is a face of , then there is a face of such that
Assuming as above, if then .
An edge belongs to a cycle iff for two distinct faces .
An edge is a cut-edge iff there exists a unique face such that .
A corollary of the above proposition is that a forest has only one face. Further, we define the length of a face as
One can define a notion of ’traversal’ (i.e., a closed walk) of a face such that the length of the closed walk is the length of the face.