Definition:Planar Graph

From ProofWiki
Jump to navigation Jump to search

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.


Examples

Arbitrary Example

This is a planar graph:

PlanarGraph.png


Complete Bipartite Graph K2,3

The complete bipartite graph $K_{2, 3}$ is a planar graph:

Complete-bipartite-graph-2-3.png


Face

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

In the above, the faces are $BCEF$, $ABF$, $CFG$, $AFG$ and $ABCDCEG$.


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 $BCEF$ is incident to:

the edges $BC, CE, EF, FB$
the vertices $B, C, E, F$.


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, $BCEF$ and $ABF$ are adjacent, but $BCEF$ and $AFG$ are not adjacent.


Non-Planar

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

This is a non-planar graph:

NonPlanarGraph.png


Also see

  • Results about planar graphs can be found here.


Sources