
handle: 11391/156253
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(n3) 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 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
