Title :
A simple parallel algorithm to draw cubic graphs
Author :
Calamoneri, Tiziana ; Olariu, Stephan ; Petreschi, Rossella
Author_Institution :
Dept. of Comput. Sci., Rome Univ., Italy
fDate :
10/1/2000 12:00:00 AM
Abstract :
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.
Keywords :
computer graphics; graphs; parallel algorithms; EREW PRAM; cubic graphs; layout area; number of bends; orthogonal grid drawing; parallel algorithm; Circuit synthesis; Computer graphics; Costs; Layout; Parallel algorithms; Phase change random access memory; Transmission line matrix methods; Visualization;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on