Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Optimal upward planarity testing of single-source digraphs

Extended abstract

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 726))

Included in the following conference series:

Abstract

A directed graph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs: we provide a new combinatorial characterization of upward planarity, and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph withn vertices is upward planar inO(n) sequential time, and inO(logn) time on a CRCW PRAM withn log logn/logn processors, usingO(n) space. The algorithm also constructs an upward planar drawing if the test is successful. The previous best result is anO(n2)-time algorithm by Hutton and Lubiw. No efficient parallel algorithms for upward planarity testing were previously known.

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 NATO Scientific Affairs Division under collaborative research grant 911016, by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council, and by the Esprit BRA of the European Community — ALCOM Contract 7141.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. P. Bertolazzi and G. Di Battista, “On Upward Drawing Testing of Triconnected Digraphs,“ Proc. ACM Symp. on Computational Geometry, pp. 272–280, 1991.

    Google Scholar 

  2. P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis, “How to Draw a Series-Parallel Digraph,” Proc. SWAT, Lecture Notes in Computer Science, vol. 621, pp. 272–283, 1992.

    Google Scholar 

  3. P. Crescenzi, G. Di Battista, and A. Piperno, “A Note on Optimal Area Algorithms for Upward Drawings of Binary Trees,“ Technical Report RAP.11.91, Dip. di Informatica e Sistemistica, Università degli Studi di Roma La Sapienza, 1991.

    Google Scholar 

  4. G. Di Battista, W.-P. Liu, and I. Rival, “Bipartite Graphs, Upward Drawings, and Planarity,” Information Processing Letters, vol. 36, pp. 317–322, 1990.

    Google Scholar 

  5. G. Di Battista and R. Tamassia, “Algorithms for Plane Representations of Acyclic Digraphs,“ Theoretical Computer Science, vol. 61, pp. 175–198, 1988.

    Google Scholar 

  6. G. Di Battista and R. Tamassia, “On-Line Graph Algorithms with SPQR-Trees,” Automata, Languages and Programming (Proc. 17th ICALP), Lecture Notes in Computer Science, vol. 442, pp. 598–611, 1990.

    Google Scholar 

  7. G. Di Battista and R. Tamassia, “On-Line Maintenance of Triconnected Components with SPOR-Trees,“ Technical Report CS-92-40, Dept. of Computer Science, Brown Univ., 1992.

    Google Scholar 

  8. G. Di Battista, R. Tamassia, and I.G. Tollis, “Area Requirement and Symmetry Display of Planar Upward Drawings, “ Discrete and Computational Geometry, vol. 7, no. 4, pp. 381–401, 1992.

    Google Scholar 

  9. P. Eades, T. Lin, and X. Lin, “Two Tree Drawing Conventions,” Technical Report No. 174, Key Centre for Software Technology, Department of Computer Science, The Univ. of Queensland, 1990.

    Google Scholar 

  10. P. Eades and R. Tamassia, “Algorithms for Automatic Graph Drawing: An Annotated Bibliography,“ Technical Report CS-89-09, Dept. of Computer Science, Brown Univ., 1989.

    Google Scholar 

  11. D. Fussell, V. Ramachandran, and R. Thurimella, “Finding Triconnected Components by Local Replacements,“ Automata, Languages and Programming (Proc. 16th ICALP), Lecture Notes in Computer Science, vol. 372, pp. 379–393, 1989.

    Google Scholar 

  12. J. Hopcroft and R.E. Tarjan, “Dividing a Graph into Triconnected Components,“ SIAM J. Computing, vol. 2, no. 3, pp. 135–158, 1973.

    Google Scholar 

  13. J. Hopcroft and R.E. Tarjan, “Efficient Planarity Testing,” J. ACM, vol. 21, no. 4, pp. 549–568, 1974.

    Google Scholar 

  14. M.D. Hutton and A. Lubiw, “Upward Planar Drawing of Single Source Acyclic Digraphs,“ Proc. ACM-SIAM Symp. on Discrete Algorithms, pp. 203–211, 1991.

    Google Scholar 

  15. M.-Y. Kao and G.E. Shannon, “Local Reorientations, Global Order, and Planar Topology,” Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 286–296, 1989

    Google Scholar 

  16. D. Kelly, “Fundamentals of Planar Ordered Sets,” Discrete Mathematics, vol. 63, pp. 197–216, 1987.

    Google Scholar 

  17. D. Kelly and I. Rival, “Planar Lattices,” Canadian J. Mathematics, vol. 27, no. 3, pp. 636–665, 1975.

    Google Scholar 

  18. A. Lempel, S. Even, and I. Cederbaum, “An Algorithm for Planarity Testing of Graphs,“ in Theory of Graphs, Int. Symposium (Rome, 1966), P. Rosenstiehl, ed., pp. 215–232, Gordon and Breach, New York, 1967.

    Google Scholar 

  19. C. Platt, “Planar Lattices and Planar Graphs,” J. Combinatorial Theory, Series B, vol. 21, pp. 30–39, 1976.

    Google Scholar 

  20. V. Ramachandran and J.H. Reif, “An Optimal Parallel Algorithm for Graph Planarity,“ Proc. IEEE Symp. on Foundations of Computer Science, 1989.

    Google Scholar 

  21. V. Ramachandran and J.H. Reif, “Planarity Testing in Parallel,“ Technical Report TR-90-15, Dept. of Computer Sciences, Univ. of Texas at Austin, 1990.

    Google Scholar 

  22. E. Reingold and J. Tilford, “Tidier Drawing of Trees,” IEEE Trans. on Software Engineering, vol. SE-7, no. 2, pp. 223–228, 1981.

    Google Scholar 

  23. I. Rival, “Graphical Data Structures for Ordered Sets,” in Algorithms and Order, ed. I. Rival, pp. 3–31, Kluwer Academic Publishers, 1989.

    Google Scholar 

  24. K.J. Supowit and E.M. Reingold, “The Complexity of Drawing Trees Nicely,“ Acta Informatica, vol. 18, pp. 377–392, 1983.

    Google Scholar 

  25. R. Tamassia, G. Di Battista, and C. Batini, “Automatic Graph Drawing and Readability of Diagrams,“ IEEE Transactions on Systems, Man and Cybernetics, vol. SMC-18, no. 1, pp. 61–79, 1988.

    Google Scholar 

  26. R. Tamassia and J.S. Vitter, “Parallel Transitive Closure and Point Location in Planar Structures,“ SIAM J. Computing, vol. 20, no. 4, pp. 708–725, 1991.

    Google Scholar 

  27. C. Thomassen, “Planar Acyclic Oriented Graphs,” Order, vol. 5, no. 4, 1989.

    Google Scholar 

  28. W.T. Trotter and J. Moore, “The Dimension of Planar Posets,” J. Combinatorial Theory, Series B, vol. 22, pp. 54–67, 1977.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IASI-CNR Viale Manzoni, 30 - 00185, Roma, Italy

    Paola Bertolazzi

  2. Dip. di Informatica e Sistemistica, Università di Roma “La Sapienza”, Via Salaria, 113 - 00198, Roma, Italy

    Giuseppe Di Battista

  3. Dip. di Statistica, Università di Roma “La Sapienza”, P.le A. Moro, 5 - 00185, Roma, Italy

    Carlo Mannino

  4. Dept. of Computer Science, Brown University, 02912-1910, Providence, RI

    Roberto Tamassia

Authors
  1. Paola Bertolazzi

    You can also search for this author inPubMed Google Scholar

  2. Giuseppe Di Battista

    You can also search for this author inPubMed Google Scholar

  3. Carlo Mannino

    You can also search for this author inPubMed Google Scholar

  4. Roberto Tamassia

    You can also search for this author inPubMed Google Scholar

Editor information

Thomas Lengauer

Rights and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R. (1993). Optimal upward planarity testing of single-source digraphs. In: Lengauer, T. (eds) Algorithms—ESA '93. ESA 1993. Lecture Notes in Computer Science, vol 726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57273-2_42

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp