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 an EREW PRAM. Our algorithm matches the time and cost performance of 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 conceptual simplicity and ease of implementation.
展开▼
