planar graph
\xyoptionall
Description
A planar graph^{} is a graph which can be drawn on a plane (a flat 2d surface) or on a sphere, with no edges crossing. When drawn on a sphere, the edges divide its area in a number of regions called faces (or “countries”, in the context of map coloring). When drawn on a plane, there is one outer country taking up all the space outside the drawing. Every graph drawn on a sphere can be drawn on a plane (puncture the sphere in the interior of any one of the countries) and vice versa. Statements on map coloring are often simpler in terms of a spherical map because the outer country is no longer a special case.
The number of faces (countries) equals $c+1$ where $c$ is the cyclomatic number, $c=mn+k$ (where $m$ is the number of edges, $n$ the number of vertices, and $k$ the number of connected components^{} of the graph). All this holds equally for planar multigraphs^{} and pseudographs^{}.
No complete graphs^{} above ${K}_{4}$ are planar. ${K}_{4}$, drawn without crossings, looks like :
$$\text{xymatrix}\mathrm{\&}A\text{ar}\mathrm{@}[d]\text{ar}\mathrm{@}[ddl]\text{ar}\mathrm{@}[ddr]\mathrm{\&}\mathrm{\&}B\text{ar}\mathrm{@}[dl]\text{ar}\mathrm{@}[dr]\mathrm{\&}C\text{ar}\mathrm{@}[rr]\mathrm{\&}\mathrm{\&}D$$ 
Hence it is planar (try this for ${K}_{5}$.)
A drawing of a planar graph is a drawing in which each edge is drawn as a line segment^{}. Every planar graph has a drawing. This result was found independently by Wagner, Fáry and Stein. Schnyder improved this further by showing how to draw any planar graph with $n$ vertices on an integer grid of $O({n}^{2})$ area.
Definition
Ideally, this definition would just formalize what was described above. It will not, exactly. It will formalize the notion of a graph with an embedding^{} into the plane.
Definition.
Let $M$ be a topological manifold^{}. Then a graph on $M$ is a pair $(G,\iota )$, where

1.
$G$ is a multigraph,

2.
$\iota $ is a function from the graph topology of $G$ into $M$, and

3.
$\iota $ is a homeomorphism^{} onto its image.
A plane graph is a graph on ${\mathbb{R}}^{2}$.
A planar graph is a graph $G$ that has an embedding $\iota $ making $(G,\iota )$ into a plane graph.
The most usual question for which this definition finds a use is “can the following graph $G$ be made into a graph on $M$?”. When $M$ is the plane, this is usually phrased as “Is $G$ a planar graph?”. Wagner’s theorem provides a criterion for answering this question. When $M$ is a torus, the answer changes: the complete bipartite graph^{} ${K}_{3,3}$ can be made into a graph on the torus.
A graph on a manifold has a notion of “face” as well as the usual graph notions of vertex and edge.
Title  planar graph 
Canonical name  PlanarGraph 
Date of creation  20130322 12:17:37 
Last modified on  20130322 12:17:37 
Owner  archibal (4430) 
Last modified by  archibal (4430) 
Numerical id  12 
Author  archibal (4430) 
Entry type  Definition 
Classification  msc 05C10 
Synonym  planar 
Related topic  WagnersTheorem 
Related topic  KuratowskisTheorem 
Related topic  CrossingLemma 
Related topic  CrossingNumber 
Related topic  FourColorConjecture 
Defines  plane graph 