A special and remarkable type of graph is one where it is possible to impose on a plane representation of the graph the condition that two edge lines do not cross each other, except in their common end vertices (in the case of edges having a common endpoint).This defines planar graphs, which play an important role in the theory because of their remarkable properties.

We will come back to this point in a later. Figure 1.1 gives an example.

Figure 1.1. A planar graph not represented in a planar way, since in this representation some edges cross not just at their endvertices. It is easy to find an appropriate representation Planar graphs have played a key role for the theory in the famous four-color theorem mentioned above. In graph terms, the theorem states that any planar graph may have its vertices colored with four different colors in such a way that two vertices joined by an edge are of different colors.