On upward drawing testing of triconnected digraphs (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On upward drawing testing of triconnected digraphs (extended abstract)

Full text

Pdf (759 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventh annual symposium on Computational geometry table of contents

North Conway, New Hampshire, United States

Pages: 272 - 280

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Paola Bertolazzi	IASI - CNR, Viale Manzoni, 30 - 00185 Roma, Italy
Giuseppe Di Battista	Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Via Salaria, 113 - 00198 Roma, Italy

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 20, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/109648.109679 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C.Berge, Graphs, North Holland, 1985.
	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.
	3	Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
	4	H.de Fraysseix and P.Rosenstiehl, "A Depth First Characterization of Planarity," Annals of Discrete Math., vol. 13, pp.75-80, 1982.
	5	Giuseppe Di Battista , Wei-Ping Liu , Ivan Rival, Bipartite graphs, upward drawings, and planarity, Information Processing Letters, v.36 n.6, p.317-322, Dec. 15, 1990 [doi>10.1016/0020-0190(90)90045-Y]
	6	Giuseppe Di Battista , Roberto Tamassia, Algorithms for plane representations of acyclic digraphs, Theoretical Computer Science, v.61 n.2-3, p.175-198, Nov. 1988 [doi>10.1016/0304-3975(88)90123-5]
	7	G.Di Battista and R.Tamassia, "Incremental Planarity Testing," Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989.
	8	G. Di Battista , R. Tamassia , I. G. Tollis, Area requirement and symmetry display in drawing graphs, Proceedings of the fifth annual symposium on Computational geometry, p.51-60, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73839]
	9	Peter Eades , Roberto Tamassia, Algorithms for Drawing Graphs: An Annotated Bibliography, Brown University, Providence, RI, 1988
	10	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	11	John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
	12	Michael D. Hutton , Anna Lubiw, Upward planar drawing of single source acyclic digraphs, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.203-211, January 28-30, 1991, San Francisco, California, United States
	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.
	14	D. Kelly, Fundamentals of planar ordered sets, Discrete Mathematics, v.63 n.2-3, p.197-216, Feb. 1987 [doi>10.1016/0012-365X(87)90008-2]
	15	D.Kelly and I.Rival, "Planar Lattices," Canad. J. Math., vol.27, pp.6 6-665, 1975.
	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.
	17	L.Lovasz, M.D.Plummer, Matching Theo~, Annals of Discrete Math., n.29, p.71, 1986.
	18	T.Nishizeki and N.Chiba, Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics, North Holland, 1988.
	19	C.Platt, "Planar Lattices and Planar Graphs," J. Combin. Theory $~r. B, vol.21, pp.30-39, 1976.
	20	I.Rival and J.Urrutia, "Representing Orders on the Plane by Translating Convex Figures," Order, vol.4, pp.319-339, 1988.
	21	D.D.Sleator, Ph.D. dissertation, Stanford University, 1980.
	22	Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
	23	C.Thomassen, ' Planar Acyclic Oriented Graphs," Order, vol.5, pp.349-361, 1989.
	24	W.Trotter and J.Moore,Jr., "The Dimension of Planar Posets,' J. Combin. Theo~ S~r. B, n.22, pp.54-67, 1977.