Definition:Planar Graph
Definition
A planar graph is a graph which can be drawn in the plane (for example, on a piece of paper) without any of the edges crossing over, that is, meeting at points other than the vertices.
 | This page has been identified as a candidate for refactoring. In particular: put this in an examples category and redraw it because it's ugly Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
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$ and $ADFEGHIHB$.
Incident
Let $G = \struct {V, E}$ 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:
Adjacent
Let $G = \struct {V, E}$ 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.
Non-Planar
A non-planar graph is a graph which is not planar.
This is a non-planar graph:
Also see
- Results about planar graphs can be found here.
Sources
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Euler's Theorem
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): planar graph