Fast algorithms for edge-coloring planar graphs

Abstract

We present two algorithms which color edges of every planar graph G with max(Δ(G), 19) colors. Therefore both algorithms produce an optimal coloring if Δ(G) ≥ 19. The first one is a linear-time sequential algorithm. The second one is a parallel EREW PRAM algorithm which runs in O(log2n) time using O(n) processors. Both algorithms are based on reduction techniques analogous to techniques used previously for vertex coloring, and both improve the best known sequential and parallel algorithms. The results are generalized to constant-genus graphs. © 1989.