In this paper we describe a parallel algorithm that, given an n vertex cubic 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 number 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 nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is an st-numbering (or Imc-numbering) computed. (C) 1998 Academic Press.
Orthogonally drawing cubic graphs in parallel / Calamoneri, Tiziana; Petreschi, Rossella. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 55:1(1998), pp. 94-108. [10.1006/jpdc.1998.1495]
Orthogonally drawing cubic graphs in parallel
CALAMONERI, Tiziana;PETRESCHI, Rossella
1998
Abstract
In this paper we describe a parallel algorithm that, given an n vertex cubic 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 number 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 nonplanar, nonbiconnected graphs. Moreover, no embedding of the graph is requested as input nor is an st-numbering (or Imc-numbering) computed. (C) 1998 Academic Press.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.