Abstract
Upward and dominance drawings of acyclic digraphs find important applications in the display of hierarchical structures such as PERT diagrams, subroutine-call charts, and is-a relationships. The combinatorial model underlying such hierarchical structures is often a series-parallel digraph. In this paper the problem of constructing upward and dominance drawings of series-parallel digraphs is investigated. We show that the area requirement of upward and dominance drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, we present parallel and sequential drawing algorithms that are optimal with respect to both the time complexity and to the area achieved. Our results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.
Research supported in part by the National Science Foundation under grant CCR-9007851, by the U.S. Army Research Office under grant DAAL03-91-G-0035, by the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-91-J-4052, ARPA order 8225, and by Cadre Technologies, Inc.
Research supported in part by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM), and by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Bertolazzi and G. Di Battista, “On Upward Drawing Testing of Triconnected Digraphs,” Proc. 7th ACM Symp. on Computational Geometry, 1991.
R. Cohen, G. Di Battista, R. Tamassia, I.G. Tollis, and P. Bertolazzi, “A Framework for Dynamic Graph Drawing,” Proc. 8th ACM Symp. on Computational Geometry, 1992.
H. de Fraysseix, J. Pach, and R. Pollack, “Small Sets Supporting Fary Embeddings of Planar Graphs,” Proc. 20th ACM Symp. on Theory of Computing, 1988.
G. Di Battista, W.P. Liu, and I. Rival, “Bipartite Graphs, Upward Drawings, and Planarity,” Information Processing Letters, 36, 317–322, 1990.
G. Di Battista, E. Pietrosanti, R. Tamassia, and I.G. Tollis, “Automatic Layout of PERT Diagrams with X-PERT,” Proc. IEEE Workshop on Visual Languages, 1989.
G. Di Battista and R. Tamassia, “Algorithms for Plane Representations of Acyclic Digraphs,” Theoretical Computer Science, 61, 175–198, 1988.
G. Di Battista, R. Tamassia, and I.G. Tollis, “Area Requirement and Symmetry Display in Drawing Graphs,” Proc. 5th ACM Symp. on Computational Geometry, 1989. To appear in Discrete & Computational Geometry.
P. Eades and R. Tamassia, “Algorithms for Drawing Graphs: an Annotated Bibliograpy,” Tech. Report CS-89-09, Brown Univ., 1989.
P. Eades and L. Xuemin, “How to Draw a Directed Graph,” Proc. IEEE Workshop on Visual Languages, 1989.
S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1979.
A. Gibbons and W. Rytter, “An Optimal Parallel Algorithm for Dynamic Expression Evaluation and its Applications,” Proc. Symp. on Foundation of Software Technology and Theoretical Computer Science, 1986.
M.D. Hutton, A. Lubiw, “Upward Planar Drawing of Single Source Acyclic Digraphs,” Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1990.
T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics, North Holland, 1988.
W. Schnyder, “Embedding Planar Graphs on the Grid,” Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1990.
K. Sugiyama, S. Tagawa, and M. Toda, “Methods for Visual Understanding of Hierarchical Systems,” IEEE Trans. on Systems, Man, and Cybernetics, SMC-11, 109–125, 1981.
R. Tamassia, G. Di Battista, and C. Batini, “Automatic Graph Drawing and Readability of Diagrams,” IEEE Trans. on Systems, Man, and Cybernetics, SMC-18, 61–79, 1988.
R. Tamassia and I.G. Tollis, “A Unified Approach to Visibility Representations of Planar Graphs,” Discrete & Comput. Geometry, 1, 321–341, 1986.
R.E. Tarjan and U. Vishkin, “Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time”, SIAM J. on Computing, 1985.
J. Valdes, R.E. Tarjan, and E.L. Lawler, “The Recognition of Series-Parallel Digraphs,” SIAM J. on Computing, 11, 298–313, 1982.
C. Thomassen, “Planar Acyclic Oriented Graphs,” Order, 5, 349–361, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bertolazzi, P., Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G. (1992). How to draw a series-parallel digraph. In: Nurmi, O., Ukkonen, E. (eds) Algorithm Theory — SWAT '92. SWAT 1992. Lecture Notes in Computer Science, vol 621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55706-7_23
Download citation
DOI: https://doi.org/10.1007/3-540-55706-7_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55706-7
Online ISBN: 978-3-540-47275-9
eBook Packages: Springer Book Archive