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.
1998
bidimensional grid; cubic graphs; orthogonal drawing; parallel algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/244831
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact