article

Upward drawings of triconnected digraphs

Authors:

G. Di Battista,

C. ManninoAuthors Info & Claims

Algorithmica, Volume 12, Issue 6

Pages 476 - 497

https://doi.org/10.1007/BF01188716

Published: 01 December 1994 Publication History

Abstract

A polynomial-time algorithm for testing if a triconnected directed graph has an upward drkwing is presented. An upward drkwing is a planar drkwing such that all the edges flow in a common direction (e.g., from bottom to top). The problem arises in the fields of automatic graph drkwing and ordered sets, and has been open for several years. The proposed algorithm is based on a new combinatorial characterization that maps the problem into a max-flow problem on a sparse network; the time complexity isO(n+r2), wheren is the number of vertices andr is the number of sources and sinks of the directed graph. If the directed graph has an upward drkwing, the algorithm allows us to construct one easily.

References

[1]

C. Berge, Graphs, North-Holland, Amsterdam, 1985.

[2]

K. Booth and G. Lueker, Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms, J. Comput. System Sci., vol. 13, pp. 335-397, 1976.

Digital Library

[3]

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees, J. Comput. System Sci., vol. 30, pp. 54-76, 1985.

Digital Library

[4]

H. de Fraysseix and P. Rosenstiehl, A Depth First Characterization of Planarity, Ann. Discrete Math., vol. 13, pp. 75-80, 1982.

[5]

G. Di Battista, W. P. Liu, and I. Rival, Bipartite Graphs, Upward Drawings, and Planarity, Inform. Process. Lett., vol. 36, pp. 317-322, 1990.

Digital Library

[6]

G. Di Banista and R. Tamassia, Algorithms for Plane Representations of Acyclic Digraphs, Theoret. Comput. Sci., vol. 61, pp. 175-198, 1988.

Digital Library

[7]

G. Di Battista and R. Tamassia, Incremental Planarity Testing, Proe. 30th IEEE Symposium on Foundations of Computer Science, pp. 436-441, 1989.

Digital Library

[8]

G. Di Battista, R. Tamassia, and I. G. Tollis, Area Requirement and Symmetry Display of Planar Upward Drawings, Discrete Comput. Geom., vol. 7, pp. 381-401, 1992.

Digital Library

[9]

P. Eades and R. Tamassia, Algorithms for Drawing Graphs: An Annotated Bibliography, Tech. Report No. CS-89-09, Brown University, 1989.

Digital Library

[10]

P. Eades and L. Xuemin, How To Draw a Directed Graph, Proc. IEEE Workshop on Visual Languages, pp. 13-17, 1989.

[11]

S. Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1979.

[12]

J. Hopcroft and R. E. Tarjan, Efficient Planarity Testing, J. Assoc. Comput. Mach., vol. 21, no. 4, pp. 549-568, 1974.

Digital Library

[13]

M.D. Hutton and A. Lubiw, Upward Planar Drawing of Single Source Acyclic Digraphs, Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms, pp. 203-211, 1991.

Digital Library

[14]

R. Jégan, R. Nowakowski, and I. Rival, The Diagram Invariant Problem for Planar Lattices, Acta Sci. Math. (Szeged), vol. 51, pp. 103-121, 1987.

[15]

D. Kelly, Fundamentals of Planar Ordered Sets, Discrete Math., vol. 63, pp. 197-216, 1987.

Digital Library

[16]

D. Kelly and I. Rival, Planar Lattices, Canad. J. Math., vol. 27, pp. 636-665, 1975.

[17]

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

[18]

L. Lovasz and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, Amsterdam, p. 71, 1986.

[19]

S.M. Malitz and A. Papakostas, On the Angular Resolution of Planar Graphs, Proc. ACM Symposium on Theory of Computing, 1992.

[20]

T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics, North-Holland, Amsterdam, 1988.

[21]

C. Platt, Planar Lattices and Planar Graphs, J. Combin. Theory Ser. B, vol. 21, pp. 30-39, 1976.

[22]

I. Rival, The Diagram, in Graphs and Orders (I. Rival, ed.), Reidel, Dordrecht, pp. 103-133, 1985.

[23]

I. Rival, Graphical Data Structures for Ordered Sets, in Algorithms and Orders (I. Rival, ed.), Kluwer, Boston, pp. 3-31, 1989.

[24]

I. Rival and J. Urrutia, Representing Orders on the Plane by Translating Convex Figures, Order, vol. 4, pp. 319-339, 1988.

[25]

K. Sugiyama, S. Tagawa, and M. Toda, Methods for Visual Understanding of Hierarchical Systems, IEEE Trans. Systems Man Cybernet., vol. 11, pp. 109-125, 1981.

[26]

R. Tamassia, On Embedding a Graph in the Grid with the Minimum Number of Bends, SIAM J. Comput., vol. 16, pp. 421-444, 1987.

Digital Library

[27]

R. Tamassia, G. Di Battista, and C. Batini, Automatic Graph Drawing and Readability of Diagrams, IEEE Trans. Systems Man Cybernet., vol. 18, pp. 61-79, 1988.

Digital Library

[28]

R. Tamassia and I. G. Tollis, A Unified Approach to Visibility Representations of Planar Graphs, Discrete Comput. Geometry, vol. 1, pp. 321-341, 1986.

Digital Library

[29]

C. Thomassen, Planar Acyclic Oriented Graphs, Order, vol. 5, pp. 349-361, 1989.

[30]

W. Trotter and J. Moore, Jr., The Dimension of Planar Posets, J. Combin. Theory Set. B, vol. 22, pp. 54-67, 1977.

[31]

G. Vijayan, Geometry of Planar Graphs with Angles, Proc. 2nd ACM Symposium on Computational Geometry, pp. 116-124, 1986.

[32]

H. Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math., vol. 54, pp. 150-168, 1932.

Cited By

Jansen BKhazaliya LKindermann PLiotta GMontecchiani FSimonov K(2023)Upward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing and Network Visualization10.1007/978-3-031-49275-4_14(203-217)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49275-4_14
Didimo WGupta SKindermann PLiotta GWolff AZehavi M(2023)Parameterized Approaches to Orthogonal CompactionSOFSEM 2023: Theory and Practice of Computer Science10.1007/978-3-031-23101-8_8(111-125)Online publication date: 15-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-23101-8_8
Chaplick SDi Giacomo EFrati FGanian RRaftopoulou CSimonov K(2022)Testing Upward Planarity of Partial 2-TreesGraph Drawing and Network Visualization10.1007/978-3-031-22203-0_13(175-187)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22203-0_13
Show More Cited By

Upward drawings of triconnected digraphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Extended path partition conjecture for semicomplete and acyclic compositions
Abstract
Let D be a digraph and let λ ( D ) denote the number of vertices in a longest path of D. For a pair of vertex-disjoint induced subdigraphs A and B of D, we say that ( A , B ) is a partition of D if V ( A ) ∪ V ( B ) = V ( D ). The Path ...
On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite ...
Computing upward topological book embeddings of upward planar digraphs
ISAAC'07: Proceedings of the 18th international conference on Algorithms and computation

This paper studies the problem of computing an upward topological book embedding of an upward planar digraph G, i.e. a topological book embedding of G where all edges are monotonically increasing in the upward direction. Besides having its own inherent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 12, Issue 6

December 1994

132 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 1994 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1994

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jansen BKhazaliya LKindermann PLiotta GMontecchiani FSimonov K(2023)Upward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing and Network Visualization10.1007/978-3-031-49275-4_14(203-217)Online publication date: 20-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49275-4_14
Didimo WGupta SKindermann PLiotta GWolff AZehavi M(2023)Parameterized Approaches to Orthogonal CompactionSOFSEM 2023: Theory and Practice of Computer Science10.1007/978-3-031-23101-8_8(111-125)Online publication date: 15-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-23101-8_8
Chaplick SDi Giacomo EFrati FGanian RRaftopoulou CSimonov K(2022)Testing Upward Planarity of Partial 2-TreesGraph Drawing and Network Visualization10.1007/978-3-031-22203-0_13(175-187)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22203-0_13
Binucci CDi Giacomo ELiotta GTappini A(2021)Quasi-upward Planar Drawings with Minimum Curve ComplexityGraph Drawing and Network Visualization10.1007/978-3-030-92931-2_14(195-209)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92931-2_14
Klawitter JZink J(2021)Upward Planar Drawings with Three and More SlopesGraph Drawing and Network Visualization10.1007/978-3-030-92931-2_11(149-165)Online publication date: 14-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-92931-2_11
Brückner GChekan V(2021)Drawing Two PosetsSOFSEM 2021: Theory and Practice of Computer Science10.1007/978-3-030-67731-2_30(410-420)Online publication date: 25-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67731-2_30
Da Lozzo GDi Battista GFrati FPatrignani MRoselli V(2020)Upward Planar MorphsAlgorithmica10.1007/s00453-020-00714-682:10(2985-3017)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s00453-020-00714-6
Hong SNagamochi H(2020)Path-Monotonic Upward Drawings of GraphsComputing and Combinatorics10.1007/978-3-030-58150-3_9(110-122)Online publication date: 29-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-58150-3_9
Brückner GHimmel MRutter I(2019)An SPQR-Tree-Like Embedding Representation for Upward PlanarityGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_39(517-531)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_39
Da Lozzo GRutter I(2019)Reaching 3-Connectivity via Edge-Edge AdditionsCombinatorial Algorithms10.1007/978-3-030-25005-8_15(175-187)Online publication date: 23-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-25005-8_15
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents