A quadratic algorithm.
The input to the algorithm will be a plane triangulation G with n vertices. (This is without loss of generality, as any planar graph can be triangulated in linear time.) The output will be a coloring of the vertices of G with four colors.
If G has at most four vertices color each vertex a different color. Otherwise if G has a vertex x of degree k < 5, then the circuit C surrounding it is a `k-ring'. Go to the k-ring analysis below. Otherwise G has minimum degree five. For every vertex we compute its charge as explained above, and find a vertex v of positive charge. It follows from our proof of Theorem 2 that either a good configuration appears in the second neighborhood of v (it which case it can be found in linear time), or a k-ring violating the definition of internal 6-connection can be found in linear time. In the latter case we go to the k-ring analysis below, in the former case we apply recursion to a certain smaller graph. A four-coloring of G can then be constructed from the four-coloring of this smaller graph in linear time.
Given a k-ring R violating the definition of internal 6-connection a procedure developed by Birkhoff can be used. We apply recursion to two carefully selected subgraphs of G. A four-coloring of G can then be constructed from the four-colorings of the two smaller graphs in linear time.
The input to the algorithm will be a plane triangulation G with n vertices. (This is without loss of generality, as any planar graph can be triangulated in linear time.) The output will be a coloring of the vertices of G with four colors.
If G has at most four vertices color each vertex a different color. Otherwise if G has a vertex x of degree k < 5, then the circuit C surrounding it is a `k-ring'. Go to the k-ring analysis below. Otherwise G has minimum degree five. For every vertex we compute its charge as explained above, and find a vertex v of positive charge. It follows from our proof of Theorem 2 that either a good configuration appears in the second neighborhood of v (it which case it can be found in linear time), or a k-ring violating the definition of internal 6-connection can be found in linear time. In the latter case we go to the k-ring analysis below, in the former case we apply recursion to a certain smaller graph. A four-coloring of G can then be constructed from the four-coloring of this smaller graph in linear time.
Given a k-ring R violating the definition of internal 6-connection a procedure developed by Birkhoff can be used. We apply recursion to two carefully selected subgraphs of G. A four-coloring of G can then be constructed from the four-colorings of the two smaller graphs in linear time.