**
Definitions**

**
Planarity** A graph is planar if it can be drawn in the plane
without edges crossing. We can test for planarity in O(n) time using algorithm
by Hopcroft and Tarjan.

*Planar
Not planar*

**
k-coloring** A graph is k-colorable if its vertices can be
colored with k colors such that no adjacent vertices are colored the same.

**
Subgraph** A graph G is a subgraph of G if its edges and
vertices for subsets of the vertex and edge sets of G. G is the supergraph of
G.

*The graph on the right is a subgraph of
the graph on the left.*

**
Induced Subgraph** A subset of vertices of graph G together with
any edges whose endpoints are both in this subset.

** Path**
A path on a graph is a sequence {x

*The blue colored edges indicate a path
between the two black vertices.*

**
Cycle** A cycle of a graph is a subset of the graph edge set of
the graph, which forms a path, the first node of which is also the last.

*The blue colored edges indicate a cycle.*

**
Smallest Vertex Ordering** - An ordering of the vertices such that
for any ordering, v

deg<v_{1},..,v_{i}>(v_{i}) = min deg<v_{1},..,v_{i}>
(v_{j}), 1 ≤ i ≤ n

** Dual
Graph** Given a planar graph G, a dual graph G of G has graph
vertices each of which correspond to a face of G and each of whose faces
correspond to a graph vertex of G. Two nodes in G are connected by an edge if
the corresponding faces in G have a boundary graph edge in common. This allows
us to turn coloring maps into coloring the vertices of the dual graph.

*1. The original graph, G.
2. Add one red vertex for each face. 3. Add edges in between "faces" that
share an edge.*

PREVIOUS: Introduction NEXT: Theorems