An optimal O(n)-time algorithm to compute an upward twopage book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n 3) time and assumes that the input series-parallel digraph does not have transitive edges. One consequence of our result is that series-parallel (undirected) graphs are necessarily sub-hamiltonian. This extends a previous result by Chung, Leighton, and Rosenberg [5] who proved subhamiltonicity for a subset of planar series-parallel graphs. Also, this paper investigates the problem of mapping planar digraphs onto a given set of points in the plane, so that the edges are drawn upward planar. This problem is called the upward point-set embedding problem. The equivalence between the problem of computing an upward two-page book embedding and an upward point-set embedding with at most one bend per edge on any given set of points is proved. An O(n log n)-time algorithm for computing an upward point-set embedding with at most one bend per edge on any given set of points for planar series-parallel digraphs is presented.

Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs

DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2002

Abstract

An optimal O(n)-time algorithm to compute an upward twopage book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n 3) time and assumes that the input series-parallel digraph does not have transitive edges. One consequence of our result is that series-parallel (undirected) graphs are necessarily sub-hamiltonian. This extends a previous result by Chung, Leighton, and Rosenberg [5] who proved subhamiltonicity for a subset of planar series-parallel graphs. Also, this paper investigates the problem of mapping planar digraphs onto a given set of points in the plane, so that the edges are drawn upward planar. This problem is called the upward point-set embedding problem. The equivalence between the problem of computing an upward two-page book embedding and an upward point-set embedding with at most one bend per edge on any given set of points is proved. An O(n log n)-time algorithm for computing an upward point-set embedding with at most one bend per edge on any given set of points for planar series-parallel digraphs is presented.
2002
9783540001584
File in 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/11391/156253
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact