Book Embeddings and PointSet Embeddings of SeriesParallel DigraphsDi Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Wismath, Stephen (2002) Book Embeddings and PointSet Embeddings of SeriesParallel Digraphs. In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 162173(Official URL: http://dx.doi.org/10.1007/3540361510_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_16
AbstractAn optimal O(n)time algorithm to compute an upward twopage book embedding of a seriesparallel digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³) time and assumes that the input seriesparallel digraph does not have transitive edges. One consequence of our result is that seriesparallel (undirected) graphs are necessarily subhamiltonian. This extends a previous resu lt by Chung, Leighton, and Rosenberg [5] who proved subhamiltonicity for a subset of planar seriesparallel 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 pointset embedding problem. The equivalence between the problem of computing an upward twopage book embedding and an upward pointset 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 pointset embedding with at most one bend per edge on any given set of points for planar seriesparallel digraphs is presented.
Actions (login required)
