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 , pp. 162-173(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_16).

Full text not available from this repository.

Abstract

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 [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.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-36151-0_16
Classifications:	P Styles > P.840 Upward M Methods > M.999 Others G Algorithms and Complexity > G.490 Embeddings G Algorithms and Complexity > G.999 Others
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/299

Actions (login required)

View Item