A Simple Way to Draw Cubic Graphs in Parallel

The main contribution of this work is to offer a simple and cost-efficient parallel algorithm that, given an arbitrary n-vertex cubic graph G as input, produces an orthogonal grid drawing of G in O(log n) time using n processors on a EREW PRAM. Our algorithm matches the time and cost performance of the best known algorithm and, at the same time, improves the constant factors of two important metrics: area and number of bends. Most importantly, our algorithm stands out by its simplicity.

PS Files

Journal Version