Orthogonally drawing cubic graphs in parallel

In this paper we describe a parallel algorithm that, given an n vertex cubi c graph G as input, outputs an orthogonal drawing of G with O(n) bends, O(n ) maximum edge length, and O(n(2)) area in O(log n) time using a CRCW PRAM with n processors. We give two slight variants of the algorithm. The first generates a drawing in which each edge has at most 2 bends; the total numbe r of bends and the area are bounded by n + 3 and (3/4 n + 3/2) x (3/4 + 3/2 ), respectively. The second optimizes the number of bends per edge (at most one) even if the values of the other functions are slightly worst. Despite its nonoptimality, this parallel algorithm is the first dealing with nonpl anar, nonbiconnected graphs. Moreover, no embedding of the graph is request ed as input nor is an st-numbering (or Imc-numbering) computed. (C) 1998 Ac ademic Press.