- 1.C.Berge, Graphs, North Holland, 1985.Google Scholar
- 2.K.Booth and G.Lueker, "Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms," J. of Computer and System Sciences, vol. 13, pp.335-397, 1976.Google ScholarDigital Library
- 3.N.Chiba, T.Nishizeki, S.Abe, and T.Ozawa, "A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees," J. of Computer and System Sciences, vol.30, pp.54-76, 1985. Google ScholarDigital Library
- 4.H.de Fraysseix and P.Rosenstiehl, "A Depth First Characterization of Planarity," Annals of Discrete Math., vol. 13, pp.75-80, 1982.Google Scholar
- 5.G.Di Battista, W.P. Liu, i.Riva}{, "Bipartite Graphs, Upward Drawings, and Planarity," Information Processing Letters, to appear. Google ScholarDigital Library
- 6.G.Di Battista and R.Tamassia, "Algorithms for Plane Representations of Acyclic Digraphs," Theoretical Computer Science, vol.61, pp.175- 198, 1988. Google ScholarDigital Library
- 7.G.Di Battista and R.Tamassia, "Incremental Planarity Testing," Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989.Google Scholar
- 8.G.Di Battista, R.Tamassia, and I.G.Tollis, "Area Requirement and Symmetry Display in Drawing Graphs," Proc. 5th A CM Symposium on Computational Geometry, 1989. Google ScholarDigital Library
- 9.P.Eades and R.Tamassia, "Algorithms for Drawing Graphs: an Annotated Bibliograpy," Tech. Report No. CS-89-09, Brown Univ., 1989. Google ScholarDigital Library
- 10.S.Even, Graph Algorithms, Computer Science Press, Rockville, MD, 1979. Google ScholarDigital Library
- 11.J.Hopcroft and R.E.Tarjan, "Efficient Planarity Testing," J. A CM, vol.21, no.4,~ pp.549-568, 1974. Google ScholarDigital Library
- 12.M.D.Hutton, A.Lubiw, "Upward }Planar Drawing of Single Source Acyclic Digraphs," Proc. and A CM-$IAM Symp. on Discrete Algorithms, (to appear) 1990. Google ScholarDigital Library
- 13.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.Google Scholar
- 14.D.Kelly, "On the Dimension of Partially Orfered Sets," Discrete Math., vol.63, pp.197-216, 1987. Google ScholarDigital Library
- 15.D.Kelly and I.Rival, "Planar Lattices," Canad. J. Math., vol.27, pp.6 6-665, 1975.Google ScholarCross Ref
- 16.A.Lempel, S.Even, and I.Cederbaum, "An Algorithm for Planarity Testing of Graphs," Theory of Graphs, International Symposium, Rome, 1966, P.Rosenstiehl, Ed., Gordon and Breach, pp.215-232, N.Y. 1967.Google Scholar
- 17.L.Lovasz, M.D.Plummer, Matching Theo~, Annals of Discrete Math., n.29, p.71, 1986.Google Scholar
- 18.T.Nishizeki and N.Chiba, Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics, North Holland, 1988.Google Scholar
- 19.C.Platt, "Planar Lattices and Planar Graphs," J. Combin. Theory $~r. B, vol.21, pp.30-39, 1976.Google ScholarCross Ref
- 20.I.Rival and J.Urrutia, "Representing Orders on the Plane by Translating Convex Figures," Order, vol.4, pp.319-339, 1988.Google ScholarCross Ref
- 21.D.D.Sleator, Ph.D. dissertation, Stanford University, 1980.Google Scholar
- 22.R,Tamassia, "On Embedding a Graph in the Grid with the Minimum Number of Bends," SIAM J. Computing, vo1.16, pp.421-444, 1987. Google ScholarDigital Library
- 23.C.Thomassen, ' Planar Acyclic Oriented Graphs," Order, vol.5, pp.349-361, 1989.Google Scholar
- 24.W.Trotter and J.Moore,Jr., "The Dimension of Planar Posets,' J. Combin. Theo~ S~r. B, n.22, pp.54-67, 1977.Google Scholar
Index Terms
- On upward drawing testing of triconnected digraphs (extended abstract)
Recommendations
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 ...
Upward drawings of triconnected digraphs
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 ...
Computing upward topological book embeddings of upward planar digraphs
ISAAC'07: Proceedings of the 18th international conference on Algorithms and computationThis 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