Definition:Planar Graph

From ProofWiki
Jump to: navigation, search


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:



The faces of a planar graph are the areas which are surrounded by edges.

In the above, the faces are $ABHC$, $CEGH$, $ACD$, $CDFE$ and $ADFEGHIHB$.


Let $G = \left({V, E}\right)$ be a planar graph:

Then a face of $G$ is incident to an edge $e$ of $G$ if $e$ is one of those which surrounds the face.

Similarly, a face of $G$ is incident to a vertex $v$ of $G$ if $v$ is at the end of one of those incident edges.

In the above graph, for example, the face $ABHC$ is incident to:

the edges $AB, BH, HC, CA$
the vertices $A, B, H, C$.


Let $G = \left({V, E}\right)$ be a planar graph.

Two faces of $G$ are adjacent if and only if they are both incident to the same edge (or edges).

In the above diagram, $ABHC$ and $ACD$ are adjacent, but $ABHC$ and $CDFE$ are not adjacent.


A non-planar graph is a graph which is not planar.

This is a non-planar graph: