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.

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
ID Code:299

Repository Staff Only: item control page

References

M. Alzohairi and I. Rival. Series-parallel ordered sets have pagenumber two. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 11-24. Springer-Verlag, 1996.

F. Bernhart and P.C. Kainen. The book thickness of a graph. J. Combin. Theory, Ser. B 27:320-331, 1979.

P. Bose. On embedding an outer-planar graph on a point set. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 25-36. Springer-Verlag, 1997.

P. Bose, M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications, 2(1):1-15, 1997.

F.R.K. Chung, F.T. Leighton, and A. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods, 8:33-58, 1987.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, October 1996.

S. Even and R.E. Tarjan. Computing an st-numbering. Theoret. Comput. Sci., 2:339-344, 1976.

J. Ganley and L. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109:215-221, 2001.

P. Gritzman, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly, 98(2):165-166, 1991.

L.S. Heath and S.V. Pemmaraju. Stack and queue layouts of posets. SIAM Journal on Discrete Mathematics, 10:599-625, 1997.

L.S. Heath and S.V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. SIAM Journal on Computing, 28:1588-1626, 1999.

L.S. Heath and S.V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part I. SIAM Journal on Computing, 28:1510-1539, 1999.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

R. Nowakowski and A. Parker. Ordered sets, pagenumbers and planarity. Order, 6:209-218, 1989.

J. Valdes, R.E. Tarjan, and E. Lawler. The recognition of series-parallel digraphs. SIAM J. Comput., 11(2):298-313, 1982.

M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38:36-67, 1989.