- A planar graph is a graph that can be drawn on a plane in such a way that no edges cross each other, and this drawing is a plane graph.
For example, in Figure 1, the first graph is a complete graph of order 4, denoted by K4, which is planar graph. The second graph is an embedding of the first graph, which is a plane graph.
- A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. Such a 1-planar drawing of G is called a 1-plane graph. Clearly, the family of 1-planar graphs is bigger than that of planar ones.
The following Figure 2 is a 1-planar graph which is constructed from a planar graph.
We can check that K5 and K3,3 (which is a complete bipartite graph) are minimal non-planar graph, but they are 1-planar graphs. Moreover, we can give 1-plane graphs of Petersen graph and 6-regular graph in Figure 3 and Figure 4, respectively.
- K5-minor free graphs
To identify nonadjacent vertices x and y of a graph G is to replace these vertices by a single vertex incident with all the edges which were incident in G with either x or y.
Let e = xy be an edge of a graph G = (V, E).
To contract an edge e of a graph G is todelete the edge and then (if the edge is a link) identify its ends. A graph H is a minor of a graph G if G has a subgraph contractible to H.
G is called H-minor free if G does not have H as a minor.
