A Parallel Algorithm for Orthogonal 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.
Conference
Version