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 it’s 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 it’s 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₁,…,x_n} such that (x₁,x₂), …, (x_n-1,x_n) are graph edges of the graph. 

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₁,…,v_n we have:

                                                deg<v₁,..,v_i>(v_i) = min deg<v₁,..,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