Definition:Planar Graph
Contents |
Planar
A planar graph is a graph which can be drawn in the plane (e.g. on a piece of paper) without any of the edges crossing over, that is, meeting at points other than the vertices.
This is a planar graph:
Face
The faces of a planar graph are the areas which are surrounded by edges.
In the above, the faces are $ABHC, CEGH, ACD, CDFE, ADFEGHIHB$.
Incident
A face is incident to an edge if the edge is one of those which surrounds the face.
Similarly, a face is incident to a vertex if the vertex is at the end of one of those incident edges.
Adjacent
Two faces are adjacent if they are both incident to the same edge (or edges).
Note that faces which are both incident to the same vertex are not considered adjacent unless they are also both incident to the same edge.
In the above diagram, $ABHC$ and $ACD$ are adjacent, but $ABHC$ and $CDFE$ are not adjacent.
Non-Planar
A non-planar graph is a graph which is not planar.
This is a non-planar graph:
