A simple parallel algorithm to draw cubic graphs

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 proces sors on an EREW PRAM. Our algorithm matches the time and cost performance o f the best previously-known algorithm while at the same time improving the constant factors involved in two important metrics: layout area and number of bends. More importantly, however, our algorithm stands out by its concep tual simplicity and ease of implementation.