## Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs
Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Wismath, Stephen
(2002)
Full text not available from this repository. ## AbstractAn optimal O(n)-time algorithm to compute an upward two-page book embedding of a series-parallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³) 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 resu lt by Chung, Leighton, and Rosenberg [5] who proved sub-hamiltonicity 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.
Repository Staff Only: item control page References |