Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs
Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Wismath, Stephen (2002) Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 162-173 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_16).
Full text not available from this repository.
An 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  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  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