A parallel algorithm for orthogonal grid drawings of cubic graphs

In this paper we present a parallel algorithm that constructs an orthogonal drawing of an $n$ vertices cubic graph with $O(n)$ bends, $O(n)$ maximum edge length and $O(n^2)$ area in $O(\log n)$ time on a CRCW PRAM with $n$ processors. We give two slight variants of the algorithm. The first one generates a drawing in which each edge has at most 2 bends, the total number of bends is $\leq n+3$, and the area is $\leq ({3 \over 4} n + {1 \over 2})^2$. The second one optimizes the number of bends for each edge (at most one) even if the values of the other functions are slightly worst. In spite of its non optimality, this parallel algorithm is the first dealing with not planar, not biconnected graphs. Moreover, neither an embedding of the graph is requested as input nor an st-numbering (or lmc-numbering) is computed.