Optimal Parallel 5-Colouring of Planar Graphs
Torben Hagerup, Marek Chrobák, Krzysztof Diks · SIAM Journal on Computing · 1989
We show that a 5-colouring of the vertices of an n-vertex planar graph may be computed in $O(\log n\log ^ * n)$ time by an exclusive-read exclusive-write parallel RAM with $O({n / {(\log n\log ^ * n)}})$ processors. Our algorithm, while faster than all previously known methods, is at the same time the first parallel 5-colouring algorithm to exhibit an optimal speedup. Optimality is achieved through a method based on the accelerating cascades technique and of independent interest. It should be emphasized that although input to the algorithm is a planar graph, we do not require a planar embedding to be given as part of the input. Other results concern the colouring of graphs of bounded genus and the construction of search structures for triangular planar subdivisions.